求解作业车间调度问题的并行模拟退火算法

摘要/Abstract

摘要： 针对作业车间调度问题，提出了一种并行模拟退火算法。该算法实行群体搜索策略，由此定义了邻域搜索规则来增强个体的搜索能力，并运用马尔科夫链分析了算法的全局收敛性。该算法在一些基准问题上得到了检验，通过与其他常规方法的比较，证明此算法可提高搜索效率，改进收敛性能。

关键词: 模拟退火, 作业车间调度, 全局收敛, 马尔科夫链

Abstract: A Parallel Simulated Annealing(PSA) algorithm was proposed for the job-shop scheduling problem. In the scheduling algorithm, the whole search strategy was applied and a rule of neighborhood search was defined to improve the performance of the individual search. Furthermore the global convergence of the algorithm was analyzed via Markov chain. The algorithm was verified on several standard benchmark problems. Compared with other traditional approaches, the efficiency of search has been increased and the convergence has been improved.

Key words: simulated annealing, job-shop scheduling, global convergence, Markov chain

中图分类号:

O244
TP18

吴大为,陆涛栋,刘晓冰,孟永胜<. 求解作业车间调度问题的并行模拟退火算法[J]. .

WU Da-wei, LU Tao-dong, LIU Xiao-bing, MENG Yong-sheng. Parallel simulated annealing algorithm for solving job-shop scheduling problem[J]. .

参考文献

［1］ LAARHOVEN P J M, AARTS E H L, LENSTRA J K. Job shop scheduling by simulated annealing ［J］. Operations Research, 1992,40(1)：113-125.

[2] GEMAN S, GEMAN D. Stochastic relaxation, gibbs distribution, and the bayyesian restoration of images［J］. IEEE Transaction Pattern Abalysis and Machine Intelligence, 1984,PAMI-6(9)：721-741.

[3] WANG Bo, ZHANG Qun, WANG Fei, et al. Quantitative analysis of infeasible solution to job shop scheduling problem ［J］. Control and Decision, 2001,16(1)：33-36(in Chinese).［王波, 张群 ,王飞，等. Job Shop排序问题解空间定量分析［J］. 控制与决策, 2001,16(1)：33-36.］

[4] STEINH FEL K, ALBRECHT A, WONG C K. Two simulated annealing-based heuristics for the job shop scheduling problem［J］. European Journal of Operational Research, 1999,118(3)：524-548.

[5] KOLONKO M. Some new results on simulated annealing applied to the job shop scheduling problem ［J］. European Journal of Operational Research, 1999,113(1)：123-136.

[6] FAN Ye, ZHOU Hong. On effective factors of simulated annealing algorithm on job-shop scheduling and an algorithm with repetitious quenching ［J］. Systems Engineering-Theory Methodology Applications, 2003,11(1)：72-76(in Chinese).［范晔, 周泓. 作业排序模拟退火算法影响因素分析和一种多次淬火模拟退火法［J］. 系统工程理论方法应用, 2003,11(1)：72-76.］

[7] FANG Zhaoben, MIU Baiqi. Stochastic processes［M］. Hefei: University of Science and Technology of China Press, 1993(in Chinese).［方兆本, 缪柏其. 随机过程［M］. 合肥: 中国科学技术大学出版社, 1993.］

[8] ZHANG Wenxiu, LEUNG Yee. Mathematical foundation of genetic algorithms［M］. Xi’an: Xi’an Jiaotong University Press, 2000(in Chinese).［张文修, 梁怡. 遗传算法的数学基础［M］. 西安: 西安交通大学出版社, 2000.］

[1]	尚正阳,顾寄南,王建平. 求解带能力约束车辆路径优化问题的改进模拟退火算法[J]. 计算机集成制造系统, 2021, 27(8): 2260-2269.
[2]	王奕祺,张晓冬. 基于仿真评价方法的适应性合作换线策略[J]. 计算机集成制造系统, 2021, 27(7): 1918-1928.
[3]	尚正阳,顾寄南,潘家保. 考虑LIFO约束的2L-CVRP优化[J]. 计算机集成制造系统, 2021, 27(7): 2134-2143.
[4]	杨艳华,姚立纲. 基于时间递推建模及交叉熵算法求解柔性作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(6): 1703-1713.
[5]	段建国,李豪晨,张青雷. 面向绿色制造的半组合式船用曲轴结构件生产车间多目标调度优化[J]. 计算机集成制造系统, 2021, 27(6): 1714-1727.
[6]	董舒豪,徐志刚,常艳茹,秦开仲,朱建峰,苏开远. 考虑物料装卸点与搬运通道的多行设施布局[J]. 计算机集成制造系统, 2021, 27(5): 1269-1280.
[7]	李海龙,陈发源,计效园,李建斌,周建新. 基于改进SPEA2算法的铸造并行车间主生产计划[J]. 计算机集成制造系统, 2021, 27(4): 1072-1080.
[8]	高鹏,苏雍贺,靳健,谢祥颖,张长志,陶飞. 基于分布式光伏运维的多类型资源调度技术[J]. 计算机集成制造系统, 2021, 27(3): 787-799.
[9]	詹欣隆,张超勇,孟磊磊,连裕翔,薛燕社. 面向高效低碳的切削参数与柔性作业车间调度集成建模与优化[J]. 计算机集成制造系统, 2021, 27(12): 3519-3535.
[10]	连裕翔,张超勇,孟磊磊,薛燕社,詹欣隆,吕畅. 基于改进Jaya算法的柔性作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(11): 3172-3184.
[11]	杨丽丽,李文龙,孔祥龙,许浩. 混合不确定性鲁棒协同优化设计方法[J]. 计算机集成制造系统, 2021, 27(11): 3282-3290.
[12]	薛玲玲. 作业车间调度的块结构邻域搜索遗传算法[J]. 计算机集成制造系统, 2021, 27(10): 2848-2857.
[13]	罗焕,陈浩杰,宋小欣,张剑. 带有缓存约束的作业车间调度求解方法[J]. 计算机集成制造系统, 2021, 27(10): 2880-2888.
[14]	黄联标,敖银辉. 基于模拟退火算法的多工段系统预防维护策略[J]. 计算机集成制造系统, 2020, 26(9): 2404-2411.
[15]	娄航宇,张吉善,赵云博. 基于扩展双资源约束型航空构件制造车间调度方法[J]. 计算机集成制造系统, 2020, 26(12): 3329-3340.