A new exact algorithm for no-wait job shop problem to minimize makespan
- PDF / 2,339,388 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 28 Downloads / 205 Views
A new exact algorithm for no‑wait job shop problem to minimize makespan A. Ozolins1 Received: 3 January 2018 / Revised: 5 May 2018 / Accepted: 3 July 2018 © Springer-Verlag GmbH Germany, part of Springer Nature 2018
Abstract In this paper, the no-wait job shop scheduling problem with a makespan objective is considered. A new exact algorithm, which is based on the dynamic programming (DP), is proposed. We introduce a dominance relation between two timetables. Several theorems are provided showing the application of the dominance. Despite the theoretical interest, experimental results prove that the proposed algorithm is able to optimally solve moderate benchmark instances within a reasonable time limit. Moreover, we have shown that the use of the dominance effectively reduces the state space of the algorithm. As an extension of the DP algorithm, we also present its heuristic version. It is shown that good quality upper bounds for large-size benchmark instances can be obtained. A comparison among several algorithms presented in the literature shows that the DP algorithm is quite competitive in terms of the computational time and the quality of obtained solutions. Keywords Job shop · No-wait · Makespan · Dynamic programming
1 Introduction In this work, the no-wait job shop scheduling (NWJS) problem with makespan minimization is considered. The NWJS problem is a type of the job shop problem where an additional no-wait constraint is included, i.e. two consecutive operations of the same job must be processed without any waiting time between machines. Lenstra and Rinnooy Kan (1979) showed that the NWJS problem is NP-hard in the strong sense. Moreover, Sahni and Cho (1979) showed that even for twomachine cases the NWJS problem belongs to the same complexity class too, i.e. strongly NP-hard problem. The NWJS problem is much more difficult than the classical job shop problem without a no-wait constraint as the experimental results have been shown by many researchers. For the NWJS problem, the * A. Ozolins [email protected] 1
University of Latvia, Zellu Street 25, Riga 1002, Latvia
13
Vol.:(0123456789)
A. Ozolins
optimality has been proven for the benchmark instances up to 20 jobs and 10 machines, or 15 jobs and 15 machines (see van den Broek 2009). However, for the classical job shop problem, the best algorithms are able to solve almost all benchmark instances with no more than 10 machines as well as several instances with 15 or 20 machines (see, for example, a summary of van Hoorn 2016). The majority of research is focussed on developing the heuristics. We will highlight the most important papers that deal with the NWJS problem with a makespan objective. Several papers developed tabu search approach. The most important research is carried out by Schuster (2006) and Bozejko and Makuchowski (2009). The latter is currently the best algorithm that is based on a tabu search approach. The first work that applies a branch and bound algorithm was proposed by Mascis and Pacciarelli (2002). Framinan and Schust
Data Loading...
