基于新型邻域结构的混合算法求解作业车间调度

doi:10.3901/JME.2016.09.141

摘要/Abstract

摘要： 针对作业车间调度问题(Job shop scheduling problem,JSP),以优化最大完工时间为目标,提出一种融合新型邻域结构的混合求解方法。混合算法由具有全局搜索能力的遗传算法和基于邻域结构的邻域搜索算法构成。在邻域结构的设计中,研究了基于甘特图的工序头尾长度计算方法,以及关键工序查找方法。通过分析已有各种邻域结构及相关理论性质,指出邻域结构的根本在于引导关键工序对机器空闲时间进行利用,并将利用方式分为两种情况：直接利用和间接利用。综合两种利用方式,科学指导关键工序的移动,根据关键工序的类型定义相应的移动操作,使其移动范围突破了工序块的内部、紧前、紧后位置限制,扩大了有效移动范围。结合43个基准算例进行测试分析,验证了所提算法具有良好的求解性能。此外,所设计的邻域结构可以进一步融合其他智能算法求解JSP问题。

关键词: 邻域结构, 邻域搜索, 遗传算法, 最大完工时间, 作业车间调度问题

Abstract: In order to optimize the maximum completion time, a hybrid solving method with a new neighborhood structure is proposed for the job shop scheduling problem (JSP). In the hybrid algorithm, genetic algorithm is adopted for global search, and local search is achieved based on neighborhood structure. In the design of the neighborhood structure, the calculation method of operation head and tail length, and the key operations searching method are studied based on Gantt chart. Through the analysis of various neighborhood structures and related theories, it points out that the foundation of neighborhood structure is to guide the key operations to utilize machine idle time, and can be divided into two types direct use and indirect use. The two utilization ways are both comprehensively considered, and the corresponding movement strategies are defined according to the type of key operations with scientific guidance. The effective movement range is expanded, breaking through the location restrictions of inside, direct adjacent before and behind of the operation block. The experimental results of 43 benchmarks show that the proposed algorithm has good performance. In addition, the new neighborhood structure can further be integrated with other intelligent algorithms for solving JSP problem.

Key words: genetic algorithm, job shop scheduling problem, local search, makespan, neighborhood structure

中图分类号:

TP301

赵诗奎. 基于新型邻域结构的混合算法求解作业车间调度[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.

参考文献

[1] TAILLARD E D. Parallel taboo search techniques for the job shop scheduling problem[J]. ORSA Journal on Computing,1994,6(2)：108-117.
[2] NOWICKI E,SMUTNICKI C. A fast taboo search algorithm for the job shop problem[J]. Management Science,1996,42(6)：797-813.
[3] NOWICKI E,SMUTNICKI C. Some new tools to solve the job-shop problem[R]. Wroclaw,Poland：Technical Report,Institute of Engineering Cybernetics,Wroclaw University of Technology,2002.
[4] BALAS E,VAZACOPOULOS A. Guided local search with shifting bottleneck for job shop scheduling[J]. Management Science,1998,44(2)：262-275.
[5] ZHANG Chaoyong,LI Peigen,GUAN Zailin,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.
[6] ZHANG Chaoyong,LI Peigen,RAO Yunqing,et al. A very fast TS/SA algorithm for the job shop scheduling problem[J]. Computers & Operations Research,2008,35(1)：282-294.
[7] NASIRI M M,KIANFAR F. A GES/TS algorithm for the job shop scheduling[J]. Computers & Industrial Engineering,2012,62(4)：946-952.
[8] GONÇALVES J F,RESENDE M G C. An extended Akers graphical method with a biased random-key genetic algorithm for job-shop scheduling[J]. International Transactions in Operational Research,2014,21(2)：215-246.
[9] PENG Bo,LÜ Zhipeng,CHENG T C E. A tabu search/path relinking algorithm to solve the job shop scheduling problem[J]. Computers & Operations Research,2015,53：154-164.
[10] 张超勇,董星,王晓娟,等. 基于改进非支配排序遗传算法的多目标柔性作业车间调度[J]. 机械工程学报,2010,46(11)：156-164.
ZHANG Chaoyong,DONG Xing,WANG Xiaojuan,et al. Improved NSGA-II for the multi-objective flexible job-shop scheduling problem[J]. Journal of Mechanical Engineering,2010,46(11)：156-164.
[11] Van 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.
[12] MATSUO H,SUH C J,SULLIVAN R S. A controlled search simulated annealing method for the general job shop scheduling problem[R]. USA,Austin,Texas： Technical Report,03-04-88,Graduate School of Business,University of Texas at Austin,1988.
[13] ZHAO Fuqing,ZHANG Jianlin,ZHANG C,et al. An improved shuffled complex evolution algorithm with sequence mapping mechanism for job shop scheduling problems[J]. Expert Systems with Applications,2015,42(8)：3953-3966.
[14] ZUO Xingquan,WANG Chunlu,TAN Wei. Two heads are better than one：An AIS- and TS-based hybrid strategy for job shop scheduling problems[J]. International Journal of Advanced Manufacturing Technology,2012,63(1-4)：155-158.
[15] REN Q,WANG Yuping. A new hybrid genetic algorithm for job shop scheduling problem[J]. Computers & Operations Research,2012,39(10)：2291-2299.
[16] GAO Liang,ZHANG Guohui,ZHANG Liping,et al. An efﬁcient memetic algorithm for solving the job shop scheduling problem[J]. Computers & Industrial Engineering,2011,60(4)：699-705.
[17] REGO C,DUARTE R. A filter-and-fan approach to the job shop scheduling problem[J]. European Journal of Operational Research,2009,194(3)：650-662.
[18] GE Hongwei,SUN Liang,LIANG Yanchun,et al. An effective PSO and AIS-based hybrid intelligent algorithm for job-shop scheduling[J]. IEEE Transactions on Systems,Man,and Cybernetics-Part A：Systems and Humans,2008,38(2)：358-368.
[19] 赵诗奎,方水良. 基于工序编码和邻域搜索策略的遗传算法优化作业车间调度[J]. 机械工程学报,2013,49(16)：160-169.
ZHAO Shikui,FANG Shuiliang. Operation-based encoding and neighborhood search genetic algorithm for job shop scheduling optimization[J]. Journal of Mechanical Engineering,2013,49(16)：160-169.
[20] 赵诗奎,方水良,顾新建. 作业车间调度的空闲时间邻域搜索遗传算法[J]. 计算机集成制造系统,2014,20(8)：1930-1940.
ZHAO Shikui,FANG Shuiliang,GU Xinjian. Idle time neighborhood search genetic algorithm for job shop scheduling[J]. Computer Integrated Manufacturing Systems,2014,20(8)：1930-1940.