双层束搜索算法优化机器人制造单元调度问题

doi:10.3778/j.issn.1002-8331.1803-0341

计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (4): 56-61.DOI: 10.3778/j.issn.1002-8331.1803-0341

双层束搜索算法优化机器人制造单元调度问题

赵晓飞1，2，郭秀萍1

1.西南交通大学经济管理学院，成都 610031
2.重庆文理学院经济管理学院，重庆 402160

出版日期:2019-02-15 发布日期:2019-02-19

Double Layers Beam Search Algorithm for Optimizing Robotic Cells Scheduling Problem

ZHAO Xiaofei1，2, GUO Xiuping1

1.School of Economics and Management, Southwest Jiaotong University, Chengdu 610031, China
2.School of Economics and Management, Chongqing University of Arts and Sciences, Chongqing 402160, China

Online:2019-02-15 Published:2019-02-19

摘要/Abstract

摘要： 针对混流生产阻塞机器人制造单元调度问题，给出了可行机器人运动插入法，构建可行解。依据可行机器人运动插入法，提出双层过滤变宽度束搜索算法进行求解。搜索过程利用局部评价函数和全局评价函数对节点进行两次择优选取。通过计算随机生成算例，仿真结果表明，相对于以分支定界算法产生的可行解进行变邻域搜索、分支定界算法、局部评价函数束搜索算法、全局评价函数束搜索算法和双层过滤定宽度束搜索算法，双层过滤变宽度束搜索算法不但能显著提高搜索效率，而且解的平均改进度分别为3.07%、6.07%、7.79%、12.62%、14.47%。

关键词: 机器人制造单元, 双层过滤变宽度束搜索, 混流生产, 阻塞, 可行机器人运动插入法

Abstract: Hybrid flow shop robotic cells scheduling problem with blocking is researched. Firstly, for constructing feasible solution, Feasible Robotic Activity Insertion Method（FRAIM） is proposed. Secondly, Double Layers Filtered Variable Width Beam Search（DLFVWBS） algorithm is developed for solving the problem according to FRAIM. During search process, to obtain promising nodes, a local evaluation function and a global evaluation function are used. Finally, compared to Variable Neighborhood Search based on the feasible solution which is generated by Branch and Bound（BBVNS）, Branch and Bound（BB） method, Beam Search according to Local evaluation function（LBS）, Beam Search based on Global evaluation function（GBS）, Double Layers Filtered Fixed Width Beam Search（DLFFWBS） algorithm, for solving stochastic generated stances, the results show that the DLFVWBS algorithm can enhance significantly the search efficiency, and the average improvement of solution is 3.07%, 6.07%, 7.79%, 12.62% and 14.47% respectively.

Key words: robotic cells, double layers filtered variable width beam search, hybrid flow shop production, blocking, feasible robotic activity insertion method

赵晓飞1，2，郭秀萍1. 双层束搜索算法优化机器人制造单元调度问题[J]. 计算机工程与应用, 2019, 55(4): 56-61.

ZHAO Xiaofei1，2, GUO Xiuping1. Double Layers Beam Search Algorithm for Optimizing Robotic Cells Scheduling Problem[J]. Computer Engineering and Applications, 2019, 55(4): 56-61.

[1]	武文杰，宋文爱，高雪梅，杨吉江，王青，黄丽萍，雷毅. 基于X线的成人OSA计算机辅助诊断综述[J]. 计算机工程与应用, 2021, 57(9): 1-8.
[2]	苏翀，任曈，王国品，殷杰. 利用决策树建立慢性阻塞性肺病中医诊断模型[J]. 计算机工程与应用, 2019, 55(3): 225-230.
[3]	宋婷，荀亚玲. 改进线程池的移动通信数据传输系统优化[J]. 计算机工程与应用, 2019, 55(24): 68-74.
[4]	王鹏辉，张宁，肖明明. 基于节点重要度的路由选择与频谱分配算法[J]. 计算机工程与应用, 2019, 55(13): 106-111.
[5]	李庆香1，赵晓飞2. 变邻域搜索算法求解机器人制造单元调度问题——排序依赖转换时间[J]. 计算机工程与应用, 2016, 52(23): 167-171.
[6]	欧阳晨星1，谭良1，2. 无尺度网络下的僵尸网络传播模型研究[J]. 计算机工程与应用, 2013, 49(9): 110-114.
[7]	王纯，徐婷婷. Householder干扰阻塞法的弱信号DOA估计[J]. 计算机工程与应用, 2013, 49(22): 231-235.
[8]	彭立，杨恒伏. 描述逻辑SHIN的ABox一致性判定算法[J]. 计算机工程与应用, 2013, 49(20): 55-62.
[9]	成淑萍1，谭良1，2，黄彪1，欧阳晨星1. 僵尸网络传播模型分析[J]. 计算机工程与应用, 2013, 49(1): 107-111.
[10]	桑玉真1，陈军华1，南理勇2. 一种基于非阻塞的分布式数据库原子提交协议[J]. 计算机工程与应用, 2012, 48(4): 128-131.
[11]	宋佩莉1，祁飞1，张鹏2. 混合蚁群蜂群算法在旅行Agent问题中的应用[J]. 计算机工程与应用, 2012, 48(36): 34-38.
[12]	郑艳伟1，2，倪宏2，邓浩江2，刘磊2. 多通道并行传输中接收缓存阻塞的缓解方法[J]. 计算机工程与应用, 2012, 48(29): 1-7.
[13]	唐富强1，于鸿洋1，张萍2. Linux下通用线程池的改进与实现[J]. 计算机工程与应用, 2012, 48(28): 77-83.
[14]	於时才，魏鑫刚. 保护信道和排队相结合的信道分配策略[J]. 计算机工程与应用, 2012, 48(1): 112-113.
[15]	苏成晓1 ，罗景青2，解礼1. 用阻塞矩阵法实现弱信号二维DOA估计[J]. 计算机工程与应用, 2011, 47(18): 153-156.

双层束搜索算法优化机器人制造单元调度问题

Double Layers Beam Search Algorithm for Optimizing Robotic Cells Scheduling Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics