机械工程学报 ›› 2019, Vol. 55 ›› Issue (16): 220-232.doi: 10.3901/JME.2019.16.220
• 交叉与前沿 • 上一篇
孙在省, 钱斌, 胡蓉, 张梓琪, 张长胜
收稿日期:
2018-12-15
修回日期:
2019-05-02
出版日期:
2019-08-20
发布日期:
2019-08-20
通讯作者:
钱斌(通信作者),男,1976年出生,教授,博士。主要研究方向为优化调度理论与方法、智能优化方法。E-mail:bin.qian@vip.163.com
作者简介:
孙在省,男,1993年出生。主要研究方向为优化调度理论与方法。E-mail:szx_1010@163.com
基金资助:
SUN Zaixing, QIAN Bin, HU Rong, ZHANG Ziqi, ZHANG Changsheng
Received:
2018-12-15
Revised:
2019-05-02
Online:
2019-08-20
Published:
2019-08-20
摘要: 针对可重入作业车间调度问题(Reentrant job shop scheduling problem,RJSSP),提出一种基于块结构性质的花粉算法(Flower pollination algorithm based on block structure properties,FPA_BSP),用于最小化总加权延误时间(Total weighted tardiness,TWT)。首先,建立RJSSP基于析取图的数学模型,并证明在确定析取弧方向后,该模型的对偶模型为最大费用流问题模型。其次,设计扩展RSOV (Reentrant-smallest-order-value,RSOV)编码规则,将花粉算法的实数矢量个体转变为排列矢量,使其可对问题解空间进行全局搜索,以发现存在优质解的区域。然后,定义8种邻域结构,并基于最大费用流问题特性分析块结构内部性质,得到前4种邻域结构能改进TWT的判定条件,可用于避免对无效区域的搜索,进而提出融合多种邻域的高效局部搜索,对全局搜索发现的优质解区域进行细致搜索。试验和算法比较验证FPA_BSP的有效性。提出RJSSP的块结构性质,并将其与花粉算法结合得到求解RJSSP的有效算法FPA_BSP,首次将花粉算法用于求解车间调度问题。
中图分类号:
孙在省, 钱斌, 胡蓉, 张梓琪, 张长胜. 基于块结构性质的花粉算法求解可重入作业车间调度问题[J]. 机械工程学报, 2019, 55(16): 220-232.
SUN Zaixing, QIAN Bin, HU Rong, ZHANG Ziqi, ZHANG Changsheng. Flower Pollination Algorithm Based on Block Structure Properties for Reentrant Job Shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2019, 55(16): 220-232.
[1] 潘全科,王凌,高亮,等. 基于差分进化与块结构邻域的作业车间调度优化[J]. 机械工程学报,2010,46(22):182-188. PAN Quanke,WANG Ling,GAO Liang,et al. Differential evolution algorithm based on blocks on critical path for job shop scheduling problems[J]. Journal of Mechanical Engineering,2010,46(22):182-188. [2] GAREY M R,JOHNSON D S,SETHI R. The complexity of flowshop and jobshop scheduling[J]. Mathematics of Operations Research,1976,1(2):117-129. [3] 唐国春,张峰,罗守成,等. 现代排序论[M]. 上海:上海科学普及出版社,2003. TANG Guochun,ZHANG Feng,LUO Shoucheng,et al. Modern scheduling theory[M]. Shanghai:Shanghai Popular Science Press,2003. [4] VAN LAARHOVEN P J M,AARTS E H L,LENSTRA J K. Job shop scheduling by simulated annealing[J]. Operations Research,1988, 40(1):113-125. [5] BALAS E. Machine sequencing via disjunctive graphs:an implicit enumeration algorithm[J]. Operations Research,1969,17(17):941-957. [6] MATSUO H,SUH C J,SULLIVAN R S. A controlled search simulated annealing method for the general job-shop scheduling problem[J]. Annals of Operations Research,1988,21(1):85-108. [7] GRABOWSKI J,NOWICKI E,SMUTNICKI C. Block algorithm for scheduling operations in a job-shop system[J]. Przeglad Statystyczny,1988,35(1):67-80. [8] GRABOWSKI J,NOWICKI E,ZDRZALKA S. A block approach for single-machine scheduling with release dates and due dates[J]. European Journal of Operational Research,1986,26(2):278-285. [9] DELL'AMICO M,TRUBIAN M. Applying tabu search to the job-shop scheduling problem[J]. Annals of Operations Research,1993,41(3):231-252. [10] NOWICKI E,SMUTNICKI C. A fast taboo search algorithm for the job shop problem[J]. Management Science,1996,42(6):797-813. [11] BALAS E,VAZACOPOULOS A. Guided local search with shifting bottleneck for job shop scheduling[J]. Management Science,1998,44(2):262-275. [12] ZHANG C Y,LI P G,GUAN Z L,et al. A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem[J]. Computers & Operations Research,2007,34(11):3229-3242. [13] ZHANG R,WU C. A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective[J]. Computers & Operations Research,2011,38(5):854-867. [14] KUHPFAHL J,BIERWIRTH C. A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective[J]. Computers & Operations Research,2016,66:44-57. [15] 赵诗奎. 基于新型邻域结构的混合算法求解作业车间调度[J]. 机械工程学报,2016,52(9):141-151. ZHAO Shikui. A hybrid algorithm with a new neighborhood structure for the job shop scheduling problem[J]. Journal of Mechanical Engineering,2016,52(9):141-151. [16] TOPALOGLU S,KILINCLI G. A modified shifting bottleneck heuristic for the reentrant job shop scheduling problem with makespan minimization[J]. International Journal of Advanced Manufacturing Technology,2009,44(7-8):781-794. [17] QIAN B,LI Z H,HU R,et al. A hybrid differential evolution algorithm for the multi-objective reentrant job-shop scheduling problem[C]//10th IEEE International Conference on Control and Automation (ICCA),Hangzhou,2013:485-489. [18] CHEN S F,QIAN B,LIU B,et al. Bayesian statistical inference-based estimation of distribution algorithm for the re-entrant job-shop scheduling problem with sequence-dependent setup times[C]//10th International Conference on Intelligent Computing (ICIC),Taiyuan,2014. Lecture Notes in Computer Science, Springer, Cham,2014,(8589):686-696. [19] YANG X S. Flower pollination algorithm for global optimization[C]//International Conference on Unconventional Computation and Natural Computation. Springer-Verlag,2012:240-249. [20] WENNINK M. Algorithmic support for automated planning boards[D]. Eindhoven,Netherlands:Technische Universiteit Eindhoven,1995. [21] KURDI M. An effective new island model genetic algorithm for job shop scheduling problem[J]. Computers & Operations Research,2016,67:132-142. |
[1] | 王春雨, 崔纳新, 李长龙, 张承慧. 基于电热耦合模型和多参数约束的动力电池峰值功率预测[J]. 机械工程学报, 2019, 55(20): 28-35. |
[2] | 马彦, 陈阳, 张帆, 陈虹. 基于扩展H∞粒子滤波算法的动力电池寿命预测方法[J]. 机械工程学报, 2019, 55(20): 36-43. |
[3] | 黄鑫, 冯旭宁, 韩雪冰, 卢兰光, 欧阳明高. 车用并联电池组不均衡电流建模与仿真分析[J]. 机械工程学报, 2019, 55(20): 44-51. |
[4] | 姜久春, 高洋, 张彩萍, 王宇斌, 张维戈, 刘思佳. 电动汽车锂离子动力电池健康状态在线诊断方法[J]. 机械工程学报, 2019, 55(20): 60-72,84. |
[5] | 李振宇, 崔长彩, 黄辉, 徐西鹏. 基于轮廓法的金刚石线锯整周三维表面形貌测量和评价[J]. 机械工程学报, 2019, 55(20): 107-115. |
[6] | 栾新, 乜云利, 李坤乾, 姜迁里, 周丽芹. 6 km自容式湍流观测剖面仪设计与试验研究[J]. 机械工程学报, 2019, 55(20): 231-239. |
[7] | 刘德民, 邓祥平, 赵永智, 段昌德, 严肃. 大型混流式模型机组动应力及压力脉动测试研究[J]. 机械工程学报, 2019, 55(19): 9-18. |
[8] | 李冰, 周德俭, 徐武彬, 张一磊. 表面波纹度对滑动轴承转子系统稳定性的影响[J]. 机械工程学报, 2019, 55(19): 51-59. |
[9] | 张微, 韩兵兵, 李响, 孙建桥, 丁千. 基于胞映射算法的转子-挤压油膜阻尼器系统多目标优化设计[J]. 机械工程学报, 2019, 55(19): 68-74. |
[10] | 贺长波, 李宏坤, 赵新维, 王维民, 吴淑明. 基于总体最小二乘准则旋转不变子空间法的叶尖定时欠采样信号分析[J]. 机械工程学报, 2019, 55(19): 103-111. |
[11] | 杨树华, 胡永, 肖忠会, 张程, 太兴宇. 柔性支承下的大型离心压缩机转子振动特性[J]. 机械工程学报, 2019, 55(19): 121-127. |
[12] | 蔡飞, 高营, 蔡习军, 张林, 张世宏, 王启民. 硬质合金刀具高能离子源增强多弧镀AlCrTiSiN梯度涂层制备及性能研究[J]. 机械工程学报, 2019, 55(19): 213-220. |
[13] | 林启敬, 伍子荣, 赵娜, 田边, 蒋庄德. 用于航空发动机的光纤F-P温度传感器及其信号解调系统研究[J]. 机械工程学报, 2019, 55(18): 1-7. |
[14] | 蔡腾飞, 潘岩, 马飞, 邱林宾, 徐平平. 喷嘴出口结构参数对风琴管射流空化作用的影响[J]. 机械工程学报, 2019, 55(18): 150-156. |
[15] | 王嘉, 张露予, 陶友瑞, 李志刚. 基于时间和当前状态的退化与冲击模型[J]. 机械工程学报, 2019, 55(18): 180-186. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||