# No-Wait Job Shop Scheduling Using a Population-Based Iterated Greedy Algorithm
## 1 Introduction  
No-wait constraints widely exist in the steel-making industry ([PERSON] [1]; [PERSON] et al. [2]), concrete manufacturing ([PERSON] and [PERSON] [3]), chemical and pharmaceutical industries ([PERSON] [4]), food industries ([PERSON] and [PERSON] [5]), and so on. The job shop problem with no-wait constraints is called the no-wait job shop scheduling problem (NWJSP) and it differs from traditional job shop problem (JSP) a lot because of the no-wait constraints. NWJSP has gained the increasing attention of researchers over decades. With regard to its complexity, NWJSP is NP (non-deterministic polynomial time)-hard in the strong sense ([PERSON] et al. [6]). [PERSON] and [PERSON] [7] proved that it is strongly NP-hard even for two machine cases. [PERSON] and [PERSON] [8] formulated it as an alternative graph and presented several heuristics and a branch and bound method. [PERSON] [9] formulated the problem as a mixed integer program (MIP) and presented a branch and bound method. Recently, [PERSON] and [PERSON] [10] provided a compact formulation of the problem and proposed an effective approach based on optimal job insertion. Due to the NP-hardness of NWJSP, the focus has been mostly on metaheuristic approaches for the problem. The pioneer work conducted by [PERSON] et al. [11] decomposed the problem into two sub-problems and gave out a two-phase tabu search algorithm that is superior to dispatching rules. [PERSON] and [PERSON] [12] presented a variable neighborhood search (VNS) algorithm and a hybrid algorithm of simulated annealing and generic algorithm (GASA). Later, [PERSON] [13] developed a fast tabu search (TS) method, and [PERSON] and [PERSON] [14] proposed a complete local search with memory (CLM). [PERSON] et al. [15] investigated the timetabling methods and developed a complete local search with limited memory (CLLM), which was shown to be comparable to the VNS, GASA and CLM. [PERSON] and [PERSON] [16] also proposed an efficient shift penalty-based timetablingmethod and further put forward a modified complete local search with memory (MCLM). [PERSON] [17] presented a neuro-evolutionary variable neighborhood search which is based on the combination of an enhanced variable neighborhood search and an artificial neural network. The proposed algorithm was shown to be applicable and effective for the problem. Very recently, [PERSON] et al. [18] proposed a branch and bound method and a particle swarm optimization algorithm for the problem. They compared the proposed algorithms with several heuristics but bypassed the other metaheuristics. [PERSON] et al. [19] improved the CLLM and developed a complete local search with memory and variable neighborhood structure (CLMMV) algorithm. The CLMMV was shown to have similar effectiveness to and better efficiency than the CLLM. More recently, [PERSON] et al. [20] proposed a hybrid artificial bee colony (HABC) algorithm and stated that the HABC outperforms the MCLM, as well as the CLLM. According to the decomposition scheme in [PERSON] et al. [11], the NWJSP can be decomposed into a timetabling problem and sequencing problem. The sequencing problem is to find a processing sequence of an optimal schedule, whereas the timetabling problem is to determine a feasible starting time for each job in the processing sequence. Using this decomposition scheme, the NWJSP can be solved in a similar way as the flow shop scheduling problem. As an effective and efficient procedure, the iterated greedy (IG) algorithm originally presented by [PERSON] and [PERSON] [21] has been applied in various scheduling environments, such as identical parallel machine scheduling [22], the distributed flow shop scheduling problem [23], and the blocking flow shop scheduling problem [24]. The IG has shown its unique potentials and advantages of fast convergence, good effectiveness, and easy implementation. In this study, we try to introduce and adapt the IG for the NWJSP.