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.
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
.
DOI: 10.3901/JME.2016.09.141
[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 efficient 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.
