A memory-based complete local search method with variable neighborhood structures for no-wait job shops

作者：Li, Xiaoping^*; Xu, Haiyan; Li, Minmin

来源：International Journal of Advanced Manufacturing Technology, 2016, 87(5-8): 1401-1408.

DOI：10.1007/s00170-013-4866-4

• No-wait job shop
• Makespan
• Local search
• Variable neighborhood structure

In this paper, the strongly NP-hard no-wait job shop problem with makespan minimization is considered. By alternatively adopting the "as early as possible" strategy or the "as late as possible" rule, an alternative delay timetabling method is constructed. The sequencing and timetabling subproblems are optimized simultaneously by calculating timetables using the proposed alternative method according to a given binary string. By integrating variable neighborhood structures, a new local search method, complete local search with memory and variable neighborhood structure (CLMMV), is presented for the considered problem. CLMMV is compared with the existing best method complete local search with limited memory (CLLM) for the considered problem on both small- and large-size benchmark instances. Experimental results show that CLMMV is similar to CLLM on effectiveness and CLMMV is much more efficient than CLLM.

• 出版日期2016-11
• 单位东南大学; 金陵科技学院