A memory and variable neighborhood structure based complete local search for the no-wait job shop problem

In this paper, an effective metaheuristic is developed for the no-wait job shop problem with the objective of makespam minimization, which is strongly NP-hard. The problem is usually decomposed into a sequencing sub-problem and a timetabling one. A partial delay timetabling method is constructed by combining the "as early as possible" strategy with the "as late as possible" rule. By integratiiig the variable neighborhood structure, a new Local Search method CLMVN (Complete Local Search with Memory and Variable Neighborhood structure) is presented for the sequencing problem. Experimental results show that CLMVN outperforms CLLM (the best algorithm for the considered problem so far) on average with less computation time.