A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem

https://doi.org/10.1016/j.cor.2005.12.002Get rights and content

Abstract

Tabu search (TS) algorithms are among the most effective approaches for solving the job shop scheduling problem (JSP) which is one of the most difficult NP-complete problems. However, neighborhood structures and move evaluation strategies play the central role in the effectiveness and efficiency of the tabu search for the JSP. In this paper, a new enhanced neighborhood structure is proposed and applied to solving the job shop scheduling problem by TS approach. Using this new neighborhood structure combined with the appropriate move evaluation strategy and parameters, we tested the TS approach on a set of standard benchmark instances and found a large number of better upper bounds among the unsolved instances. The computational results show that for the rectangular problem our approach dominates all others in terms of both solution quality and performance.

Introduction

The job shop scheduling problem with objective of minimizing makespan of the schedule, JCmax, has a very wide engineering background. The problem can be briefly described as follows. There are a set of jobs and a set of machines. Each job consists of a sequence of operations, and each of the operations uses one of the machines for a fixed duration. Each machine processes at most one operation at one time. Once the operation started, no preemption is permitted. A scheduling is an assignment of operations to time intervals on the machines. The objective of the problem is to find a schedule which minimizes the makespan (Cmax), that is, the finish time of the last operation completed.

The JSP is among the hardest combinatorial optimization problems. Since it is an important practical problem, JSP has been studied by a significant number of researchers, and many optimization algorithms and approximation algorithms have been proposed. The optimization algorithms, which are mainly based on the B&B scheme such as Carlier and Pinson [1] and Brucker et al. [2], have been successfully applied in solving small instances. However, they could not solve instances larger than 250 operations in a reasonable time. On the other hand, approximation algorithms, which include priority dispatch, shifting bottleneck approach, meta-heuristic methods and so on, provide a quite good alternative for the JSP. Approximation algorithms were firstly developed on the basis of dispatching rules, which are very fast, but the quality of solutions that they provide usually leaves plenty of room for improvement. A more elaborate algorithm, which could produce considerably better approximations at a higher computational cost, is the shifting bottleneck approach proposed by Adams et al. [3]. More recently, the meta-heuristic methods, such as genetic algorithm (GA) [4], simulated annealing (SA) [5], tabu search (TS) [6], [7], could provide the high-quality solutions with reasonable computing times and have captured the attention of many researchers. The relevant surveys can be seen from Vaessens et al. [8], Blażewicz et al. [9] and Jain and Meeran [10].

Within the class of meta-heuristic methods, Tabu search, initially proposed by Glover [11], seems to be one of the most promising methods for the job shop scheduling problem with the makespan criterion. Tabu search was firstly applied to the JSP by Taillard [12], whose main contribution was the use of the neighborhood structure introduced by Van Laarhoven et al. [5] and proposed a fast estimation strategy. Taillard observed that this algorithm has a higher efficiency for rectangular instances. Since then, researchers have introduced numerous improvements to Taillard's original algorithm, and the most important contributions include Nowicki and Smutnicki [7], Dell’Amico and Trubian [13], Barnes and Chambers [14] and Chambers and Barnes [15]. Among these individual TS methods, algorithm TSAB designed by Nowicki and Smutnicki [7] introduces the real breakthrough in both efficiency and effectiveness for the JSP. For example, it finds the optimal solution for the notorious instance FT10 within only 30 s on a now-dated personal computer. The i-TSAB technique of Nowicki and Smutnicki [16], which is an extension of their earlier TSAB algorithm, represents the current state-of-the-art approximation algorithm for the JSP and improves the majority of upper bounds of the unsolved instances.

With tabu search algorithms for the JSP being improved, different neighborhood structures and evaluation strategies have been proposed in order to make the search more effective and efficient. In this paper, by thoroughly studying the previous neighborhood strategies, we propose a new enhanced neighborhood structure to solve job shop scheduling problem by TS approach. Our approach was tested on a set of standard benchmark instances and found 54 better upper bounds for the unsolved instances. The remainder of this paper is organized as follows. Section 2 gives the representation of the job shop scheduling problem. In Section 3, the new neighborhood structure and the implementation of tabu search approach are provided. In Section 4, we firstly present the comparison of the different neighborhood structures and comparison of move evaluation strategies respectively, and then give the computational study on the benchmark problems. Conclusion is presented in Section 5.

Section snippets

Representation of the JSP

The job shop scheduling problem can be represented with a disjunctive graph introduced by Balas [17]. Let J={1,2,,n} be the set of jobs, M={1,2,,m} the set of machines. A disjunctive graph G(V,A,E) is defined as follows: V is {0,1,2,,n˜} the set of nodes representing all operations where 0 and n˜ represent the dummy start and finish operations, respectively. A is the set of conjunctive (directed) arcs connecting consecutive operations of the same job, and E is the set of disjunctive arcs

Tabu search algorithm for the JSP

The tabu search, defined and developed primarily by Glover [18], [19], [20], has been successfully applied to a large number of combinatorial optimization problems, especially in production scheduling domain. TS is an enhancement of the well-known hill climbing heuristic, which use a memory function to avoid being trapped at a local minimum. The TS procedure is generally simple. The procedure starts with a feasible initial solution and stores it as the current seed and the best solution. The

Computational experiments

The enhanced dynamic TS (TSED) algorithm described above was implemented in VC++ language on personal computer Pentium IV1.8G and tested on a large number of standard instances taken from the literature. These job shop scheduling instances include the following classes4: three instances denoted as (FT6, FT10, FT20) due to Fisher and Thompson [24], forty instances (LA01–LA40) due to Lawrence [25], five instances (ABZ5–ABZ9) due to Adams et al. [3], twenty instances (SWV01–SW 20) due to Storer et

Conclusion

The effectiveness and efficiency of the tabu search for the JSP depend on the neighborhood structures and move evaluation strategies. However, in order for search to be more efficient, the neighborhood structures defined in the JSP are becoming more and more constrained at present, such as the highly restrictive neighborhood of the Nowicki and Smutnicki. Consequently, this TS algorithm is prone to trap at a local minimum, and the recency-based memory with the recovery of elite solutions and

Acknowledgements

This paper is supported by the National Basic Research Program of China (under the Grant no. 2005CB724107) and the National Natural Science Foundation, China (under the Grants no. 50305008, 70271053). The authors would like to thank the referees for their helpful comments and suggestions.

References (31)

  • P.J.M. Van Laarhoven et al.

    Job shop scheduling by simulated annealing

    Operations Research

    (1992)
  • É.D. Taillard

    Parallel taboo search techniques for the job-shop scheduling problem

    ORSA Journal on Computing

    (1994)
  • E. Nowicki et al.

    A fast taboo search algorithm for the job shop scheduling problem

    Management Science

    (1996)
  • R.J.M. Vaessens et al.

    Job shop scheduling by local search

    INFORMS Journal on Computing

    (1996)
  • Taillard ÉD. Parallel taboo search technique for the job shop scheduling problem. Technical Report ORWP 89/11, DMA,...
  • Cited by (254)

    View all citing articles on Scopus
    View full text