| Abstract: | 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. |
