×

A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. (English) Zbl 1123.90041

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

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

Tabu search
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Carlier, J.; Pinson, E., An algorithm for solving the job shop problem, Management Science, 35, 29, 164-176 (1989) · Zbl 0677.90036
[2] Brucker, P.; Jurisch, B.; Sievers, B., A branch and bound algorithm for job-shop scheduling problem, Discrete Applied Mathematics, 49, 105-127 (1994) · Zbl 0802.90057
[3] Adams, J.; Balas, E.; Zawack, D., The shifting bottleneck procedure for job shop scheduling, Management Science, 34, 391-401 (1988) · Zbl 0637.90051
[4] Croce, F. D.; Tadei, R.; Volta, G., A genetic algorithm for the job shop problem, Computers & Operations Research, 22, 15-24 (1995) · Zbl 0816.90081
[5] Van Laarhoven, P. J.M.; Aarts, E. H.L.; Lenstra, J. K., Job shop scheduling by simulated annealing, Operations Research, 40, 1, 113-125 (1992) · Zbl 0751.90039
[6] Taillard, É. D., Parallel taboo search techniques for the job-shop scheduling problem, ORSA Journal on Computing, 6, 108-117 (1994) · Zbl 0807.90066
[7] Nowicki, E.; Smutnicki, C., A fast taboo search algorithm for the job shop scheduling problem, Management Science, 42, 6, 797-813 (1996) · Zbl 0880.90079
[8] Vaessens, R. J.M.; Aarts, E. H.L.; Lenstra, J. K., Job shop scheduling by local search, INFORMS Journal on Computing, 8, 302-317 (1996) · Zbl 0863.90094
[9] Blażewicz, J.; Domschke, W.; Pesch, E., The job shop scheduling problem: conventional and new solution techniques, European Journal of Operational Research, 93, 1-33 (1996) · Zbl 0980.90024
[10] Jain, A. S.; Meeran, S., Deterministic job shop scheduling: past, present and future, European Journal of Operational Research, 113, 390-434 (1999) · Zbl 0938.90028
[11] Glover, F., Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, 13, 533-549 (1986) · Zbl 0615.90083
[12] Taillard ÉD. Parallel taboo search technique for the job shop scheduling problem. Technical Report ORWP 89/11, DMA, Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland, 1989.; Taillard ÉD. Parallel taboo search technique for the job shop scheduling problem. Technical Report ORWP 89/11, DMA, Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland, 1989.
[13] Dell’Amico, M.; Trubian, M., Applying tabu-search to job-shop scheduling problem, Annals of Operations Research, 41, 1-4, 231-252 (1993) · Zbl 0771.90056
[14] Barnes, J. W.; Chambers, J. B., Solving the job shop scheduling problem using tabu search, IIE Transactions, 27, 257-263 (1995)
[15] Chambers JB, Barnes JW. New tabu search results for the job shop scheduling problem. Technical Report ORP96-10, Graduate Program in Operations Research and Industrial Engineering, The University of Texas at Austin, 1996.; Chambers JB, Barnes JW. New tabu search results for the job shop scheduling problem. Technical Report ORP96-10, Graduate Program in Operations Research and Industrial Engineering, The University of Texas at Austin, 1996.
[16] Nowicki E, Smutnicki C. Some new tools to solve the job shop problem. Technical Report 60/2002, Institute of Engineering Cybernetics, Technical University of Wroclaw, Wroclaw, Poland, 2002.; Nowicki E, Smutnicki C. Some new tools to solve the job shop problem. Technical Report 60/2002, Institute of Engineering Cybernetics, Technical University of Wroclaw, Wroclaw, Poland, 2002.
[17] Balas, E., Machine sequencing via disjunctive graph: an implicit numeration algorithm, Operations Research, 17, 941-957 (1969) · Zbl 0183.49404
[18] Glover, F., Tabu search—Part I, ORSA Journal on Computing, 1, 3, 190-206 (1989) · Zbl 0753.90054
[19] Glover, F., Tabu search—Part II, ORSA Journal on Computing, 2, 1, 4-32 (1990) · Zbl 0771.90084
[20] Glover, F.; Laguna, M., Tabu search (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0930.90083
[21] Matsuo HD, Suh CJ, Sullivan RS. A controlled search simulated annealing method for general job shop scheduling problem. Working Paper, 03-04-88, Department of Management, The University of Texas at Austin, Austin, TX, 1988.; Matsuo HD, Suh CJ, Sullivan RS. A controlled search simulated annealing method for general job shop scheduling problem. Working Paper, 03-04-88, Department of Management, The University of Texas at Austin, Austin, TX, 1988.
[22] Balas, E.; Vazacopoulos, A., Guided local search with shifting bottleneck for job shop scheduling, Management Science, 44, 2, 262-275 (1998) · Zbl 0989.90057
[23] Ten Eikelder, H. M.M.; Aarts, B. J.M.; Verhoeven, M. G.A.; Aarts, E. H.L., Sequential and paralled local search algorithms for job shop scheduling, (Voss, S.; Martello, S.; Osman, I. H.; Roucairol, C., Meta-HeuristicAdvances and Trends in Local Search Paradigms for Optimization (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Massachusetts), 359-371 · Zbl 0970.90066
[24] Fisher, H.; Thompson, G. L., Probabilistic learning combinations of local job-shop scheduling rules, (Muth, J. F.; Thompson, G. L., Industrial scheduling (1963), Englewood Cliffs, NJ: Englewood Cliffs, NJ Prentice-Hall), 225-251
[25] Lawrence S. Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (Supplement). Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania, 1984.; Lawrence S. Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (Supplement). Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania, 1984.
[26] Storer, R. H.; Wu, S. D.; Vaccari, R., New search spaces for sequencing problems with applications to job-shop scheduling, Management Science, 38, 10, 1495-1509 (1992) · Zbl 0759.90048
[27] Yamada, T.; Nakano, R., A genetic algorithm applicable to large-scale job-shop problems, (Manner, R.; Manderick, B., Proceedings of the second international workshop on parallel problem solving from nature (PPSN’2) (1992), Brussels: Brussels Belgium), 281-290
[28] Demirkol, E.; Mehta, S.; Uzsoy, R., Benchmarks for shop scheduling problems, European Journal of Operational Research, 109, 137-141 (1998) · Zbl 0951.90022
[29] Geyik, F.; Cedimoglu, I. H., The strategies and parameters of tabu search for job-shop scheduling, Journal of Intelligent Manufacturing, 15, 439-448 (2004)
[30] Pezzella, F.; Merelli, E., A tabu search method guided by shifting bottleneck for job shop scheduling problem, European Journal of Operational Research, 120, 297-310 (2000) · Zbl 0953.90026
[31] Steinhöfel, K.; Albrecht, A.; Wong, C. K., An experimental analysis of local minima to improve neighbourhood search, Computers & Operations Research, 30, 2157-2173 (2003) · Zbl 1039.90101
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.