Abstract
This paper deals with the classic job-shop scheduling problem with makespan criterion. Some new properties of the problem associated with blocks are presented and discussed. These properties allow us to propose a new, very fast local search procedure based on a tabu search approach. The central concepts are lower bounds for evaluations of the moves, and perturbations that guide the search to the more promising areas of solution space, where "good solutions" can be found. Computational experiments are given and compared with the results yielded by the best algorithms discussed in the literature. These results show that the algorithm proposed solves the job-shop instances with high accuracy in a very short time. The presented properties and ideas can be applied in many local search procedures.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Aarts, E. and J.K. Lenstra (1997) Local Search in Combinatorial Optimization. Wiley, New York.
Adams, J., E. Balas and D. Zawack (1988) "The Shifting Bottleneck Procedure for Job-Shop Scheduling," Management Science, 34(6):391–401.
Applegate, D. and W. Cook (1991) "A Computational Study of the Job-Shop Scheduling Problem," ORSA Journal of Computing, 3:149–156.
Balas, E. (1969) "Machine Sequencing via Disjunctive Graphs: An Implicit Enumeration Algorithm," Operations Research, 17:941–957.
Balas, E. and A. Vazacopoulos (1998) "Guided Local Search with Shifting Bottleneck for Job-Shop Scheduling," Management Science, 44(2):262–275.
Carlier, J. (1982) "The One-Machine Sequencing Problem," European Journal of Operational Research, 1:42–47.
Carlier, J. and E. Pinson (1989) "An Algorithm for Solving the Job Shop Problem," Management Science, 35:164–176.
Dongarra, J.J. (2004) Performance of Various Computers using Standard Linear Equations Software. Working paper. Computer Science Department, University of Tennessee, USA. http://www.netlib.org/benchmark/performance.ps.
DellAmico, M. and M. Trubian (1993) "Applying Tabu Search to the Job-Shop Scheduling Problem," Annals of Operations Research, 4:231–252.
Fisher, H. and G.L. Thompson (1963) Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules. In J.F. Muth, G.L. Thompson, Editors, Industrial Scheduling, Prencite-Hall, Englewood Cliffs, New York.
Glover, F. (1989) "Tabu search. Part I," ORSA Journal of Computing, 1:190–206.
Glover, F. (1990) "Tabu search. Part II," ORSA Journal of Computing, 2:4–32.
Grabowski, J. (1979) Generalized problems of operations sequencing in the discrete production systems. (Polish), Monographs 9, Scientific Papers of the Institute of Technical Cybernetics of Wroclaw Technical University.
Grabowski, J. (1980) "On Two-Machine Scheduling with Release and Due Dates to Minimize Maximum Lateness," Opsearch, 17:133–154.
Grabowski, J. (1982) A new Algorithm of Solving the Flow-Shop Problem. In G. Feichtinger and P. Kall, Editors, Operations Research in Progress, Reidel Publishing Company, Dordrecht, 57–75.
Grabowski, J., E. Skubalska and C. Smutnicki (1983) "On Flow-Shop Scheduling with Release and Due Dates to Minimize Maximum Lateness," Journal of the Operational Research Society, 34:615–620.
Grabowski, J., E. Nowicki and S. Zdrzalka (1986) "A Block Approach for Single Machine Scheduling with Release Dates and Due Dates," European Journal of Operational Research, 26:278–285.
Grabowski, J. and J. Janiak (1987) "Job-Shop Scheduling with Resource-Time Models of Operations," European Journal of Operational Research, 28:58–73.
Grabowski, J., E. Nowicki and C. Smutnicki (1988) Block Algorithm for Scheduling of Operations in Job-Shop System. (Polish), Przeglad Statystyczny, 35:67–80.
Grabowski, J. and J. Pempera (2001) New Block Properties for the Permutation Flow-Shop Problem with Application in TS. Journal of the Operational Research Society, 52:210–220. Intemet, http://mscmga.ms.ic.ac.uk/info.html.
Laarhoven, P.V., E. Aarts and J.K. Lenstra (1992) "Job-Shop Scheduling by Simulated Annealing," Operations Research, 40:113–125.
Lawrence, S. (1984) Supplement to "Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques," Technical Report, GSIA, Carnegie Mellon University.
Matsuo, H., C.J. Suh and R.S. Sullivan (1988) Controlled Search Simulated Annealing Method for the General Job-Shop Scheduling Problem. Working Paper 03-04-88, Department of Management, Graduate School of Business, The University of Texas at Austin.
Morton, T. and D. Pentico (1993) Heuristic Scheduling Systems. Wiley, New York.
Nowicki, E. and C. Smutnicki (1996a) "A Fast Tabu Search Algorithm for the Permutation Flow-Shop Problem," European Journal of Operational Research, 91:160–175.
Nowicki, E. and C. Smutnicki (1996b) "A Fast Tabu Search Algorithm for the Job-Shop Problem," Management Science, 42(6):97–813.
Pezzella, F. and E. Merelli (2000) "A Tabu Search Method Guided by Shifting Bottleneck for the Job-Shop Scheduling Problem". European Journal of Operational Research, 120:297–310.
Smutnicki, C. (1998) A Two-Machine Permutation Flow-Shop Scheduling with Buffers. OR Spectrum, 20:229–235.
Taillard, E. (1993) "Benchmarks for Basic Scheduling Problems," European Journal of Operational Research, 64:278–285.
Vaessens, R., E. Aarts and J.K. Lenstra (1996) "Job Shop Scheduling by Local Search," INFORMS Journal of Computing, 8:303–317.
Zdrzalka, S. and J. Grabowski (1989) "An Algorithm for Single Machine Sequencing with Release Dates to Minimize Maximum Cost," Discrete Applied Mathematics, 23:73–89.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Kluwer Academic Publishers
About this chapter
Cite this chapter
Grabowskil, J., Wodecki, M. (2005). A Very Fast Tabu Search Algorithm for Job Shop Problem. In: Sharda, R., Voß, S., Rego, C., Alidaee, B. (eds) Metaheuristic Optimization via Memory and Evolution. Operations Research/Computer Science Interfaces Series, vol 30. Springer, Boston, MA. https://doi.org/10.1007/0-387-23667-8_5
Download citation
DOI: https://doi.org/10.1007/0-387-23667-8_5
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4020-8134-7
Online ISBN: 978-0-387-23667-4
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)