求解作业车间调度问题的广义粒子群优化算法

摘要/Abstract

摘要： 为克服传统粒子群优化算法在解决组合优化问题上的局限性，分析了其优化机理，并在此基础上提出了广义粒子群优化模型。按照此模型提出了一种求解作业车间调度问题的广义粒子群优化算法。在本算法中，利用遗传算法中的交叉操作作为粒子间的信息交换策略，利用遗传算法中的变异操作作为粒子的随机搜索策略，而粒子的局部搜索策略则采用禁忌搜索来实现。为了控制粒子的局部搜索以及向全局最优解的收敛，迭代过程中交叉概率以及禁忌搜索的最大步长都是动态变化的。实验结果表明，本算法可有效地求解作业车间调度问题，验证了广义粒子群优化模型的合理性。

关键词: 粒子群优化, 遗传算法, 禁忌搜索, 作业车间调度

Abstract: To overcome the limitations of traditional Particle Swarm Optimization (PSO) on solutions to the combinatorial optimization problems, a General PSO (GPSO) model was proposed after analyzing the optimization mechanism of the traditional PSO. Based on this model, a GPSO algorithm was presented to solve the Job-shop Scheduling Problem (JSP). In GPSO, crossover and mutation operations in genetic algorithm were respectively utilized by particles to exchange information and search randomly. Besides, Tabu Search was used for particles local search. To control the local search and ensure its convergence to the global optimum solution, time-varying crossover probability and time-varying maximum step size of Tabu Search were introduced. The experimental results showed that JSP could be solved by GPSO effectively. The feasibility of the proposed GPSO model was also demonstrated.

Key words: particle swarm optimization, genetic algorithm, tabu search, job-shop scheduling

中图分类号:

TP278

彭传勇，高亮，邵新宇，周驰. 求解作业车间调度问题的广义粒子群优化算法[J]. .

>PENG Chuan-yong,GAO Liang,SHAO Xin－yu，ZHOU Chi. General particle swarm optimization algorithm for job-shop scheduling proble[J]. .

参考文献

［1］ KENNEDY J,EBERHART R C.Particle swarm optimization［A］.Proceedings of IEEE International Conference on Neural Networks［C］.Piscataway,NJ,USA:IEEE Service Center,1995.1942-1948.

[2] YANG Wei,LI Qiqiang.Survey on particle swarm optimization algorithm［J］.Engineering Science,2004,6(5):87-94(in Chinese).［杨维，李歧强.粒子群优化算法综述［J］.中国工程科学,2004，6(5)：87-94.］

[3] IOAN C T.The particle swarm optimization algorithm:convergence analysis and parameter selection［J］.Information Processing Letters,2003,85(6):317-325.

[4] GAO Haibing,GAO Liang,ZHOU Chi,et al.Particle swarm optimization based algorithm for neural network learning［J］.ACTA Electronical Sinice，2004,32(9):1572-1574(in Chinese).［高海兵，高亮，周驰，等.基于粒子群优化的神经网络训练算法研究［J］.电子学报，2004，32(9)：1572-1574.］

[5] CARLOS A C,GREGORIO T P,MAXIMINO S L.Handing multiple objectives with particle swarm optimization［J］.IEEE Transaction on Evolutionary Computation,2004,8(3):256-279.

[6] HE Z,WEI C.Extracting rules from fuzzy neural network by particle swarm optimization［A］.Proceedings of IEEE International Conference on Evolutionary Computation［C］.Piscataway,NJ,USA:IEEE Service Center,1998.74-77.

[7] WANG Kangping， HUANG Lan， ZHOU Chunguang，et al.Particle swarm optimization for traveling salesman problem［A］.Proceedings of the Second International Conference on Machine Learning and Cybernetics［C］.Piscataway,NJ,USA:IEEE Service Center,2003.1583-1585.

[8] TASGETIREN M F,SEVKLI M,LIANG Y,et al.Particle swarm optimization algorithm for single machine total weighted tardiness problem［A］.Congress on Evolutionary Computation［C］.Piscataway,NJ,USA:IEEE Service Center,2004.1412-1419.

[9] CAREY E L,JOHNSON D S,SETHI R.The complexity of flowshop and job-shop scheduling［J］.Mathematics of Operations Research,1976,1(2):117-129.

[10] CROCE F D,TADEI R,VOLTA G.A genetic algorithm for the job shop problem［J］.Computers & Operations Research,1995,22(1):15-24.

[11] ZHANG Chaoyong,RAO Yunqing,LI Peigen,et al.An improved genetic algorithm for job-shop scheduling［J］.Computer Integrated Manufacturing Systems,2004,10(8):966-970(in Chinese).［张超勇，饶运清，李培根，等.求解作业车间调度问题的一种改进遗传算法［J］.计算机集成制造系统,2004,10(8):966-970.］

[12] BEATRICE M O,MARIO V.Local search genetic algorithms for the job shop scheduling problem［J］.Applied Intelligence,2004,21(1):99-109.

[13] 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-126.

[14] PEZZELLA F,MERELLI E.A tabu search method guided by shifting bottleneck for the job shop scheduling problem［J］.European Journal of Operational Research,2000,120(2):297-310.

[15] FARUK G.The strategies and parameters of tabu search for job-shop scheduling［J］.Journal of Intelligent Manufacturing,2004,15(4):439-448.

[16] TONG Gang,LI Guangquan,LIU Baokun.A modified taboo search algorithm for the job-shop problem［J］.Systems Engineering-Theory & Practice,2001,21(9):48-52(in Chinese).［童刚，李光泉，刘宝坤.一种用于Jop-Shop调度问题的改进禁忌搜索算法［J］.系统工程理论与实践，2001,21(9):48-52.］

[17] ZHOU Pin,LI Xiaoping,ZHANG Hongfang.An ant colony algorithm for job shop scheduling problem［A］.Fifth World Congress on Intelligent Control and Automation［C］.Piscataway,NJ,USA:IEEE Service Center,2004.2899-2903.

[18] JOSE F G,JORGE J M,MAURICIO G R.A hybrid genetic algorithm for the job shop problem［R］.NJ,USA:AT&T Labs Research,2002.

[1]	陈年,金涛,王建民. 基于变异反馈的临床路径优化[J]. 计算机集成制造系统, 2021, 27(9): 2556-2564.
[2]	李国明,李军华. 带软时间窗随机需求车辆路径问题的算法研究[J]. 计算机集成制造系统, 2021, 27(8): 2270-2281.
[3]	黎英杰,刘建军,陈庆新,毛宁. 多层级装配作业车间等量分批策略与调度算法[J]. 计算机集成制造系统, 2021, 27(8): 2307-2320.
[4]	冯国奇,崔东亮,代学武,俞胜平. 数据视角下神经网络增量学习支持的涡轮盘多目标优化[J]. 计算机集成制造系统, 2021, 27(8): 2393-2404.
[5]	王文中,张树生,余隋怀,陈登凯. 基于解构·重构思维的潜水器舱室布局优化[J]. 计算机集成制造系统, 2021, 27(7): 2045-2052.
[6]	杨艳华,姚立纲. 基于时间递推建模及交叉熵算法求解柔性作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(6): 1703-1713.
[7]	段建国,李豪晨,张青雷. 面向绿色制造的半组合式船用曲轴结构件生产车间多目标调度优化[J]. 计算机集成制造系统, 2021, 27(6): 1714-1727.
[8]	李永湘,姚锡凡,刘敏. 基于可靠性可信性分析的云制造服务组合优化[J]. 计算机集成制造系统, 2021, 27(6): 1780-1798.
[9]	王勇,周雪,刘永,许茂增. 基于车辆共享的多中心共同配送联盟优化[J]. 计算机集成制造系统, 2021, 27(6): 1820-1832.
[10]	张昊鹏,郭宇,汤鹏洲,黄少华,刘道元,李晗. 基于图像匹配的增强现实装配系统跟踪注册方法[J]. 计算机集成制造系统, 2021, 27(5): 1281-1291.
[11]	胡金昌,刘紫薇,马文凯,吴耀华. 考虑学习效应的单人作业车间多目标调度算法[J]. 计算机集成制造系统, 2021, 27(5): 1361-1370.
[12]	刘俊琦,张则强,王沙沙,曾艳清. 考虑不规则物流交互点的过道布置问题建模与优化[J]. 计算机集成制造系统, 2021, 27(4): 1155-1166.
[13]	葛显龙,冉小芬. 基于时间窗指派的污染路径问题[J]. 计算机集成制造系统, 2021, 27(4): 1178-1187.
[14]	夏扬坤,邓永东,庞燕,王忠伟,高亮. 带客户分级和需求可拆分的生鲜车辆路径问题[J]. 计算机集成制造系统, 2021, 27(4): 1238-1248.
[15]	裴小兵,李依臻. 新型混合改进遗传算法求解零等待流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(3): 815-827.