×

Ant colony optimization combined with taboo search for the job shop scheduling problem. (English) Zbl 1180.90123

Summary: We present a hybrid algorithm combining the ant colony optimization algorithm with the taboo search algorithm for the classical job shop scheduling problem. Instead of using the conventional construction approach to construct feasible schedules, the proposed ant colony optimization algorithm employs a novel decomposition method inspired by the shifting bottleneck procedure, and a mechanism of occasional reoptimizations of partial schedules. Besides, a taboo search algorithm is embedded to improve the solution quality. We run the proposed algorithm on 101 benchmark instances and obtain competitive results and a new best upper bound for one open benchmark instance is found.

MSC:

90B35 Deterministic scheduling theory in operations research

Keywords:

makespan

Software:

JOBSHOP; Beam-ACO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Garey, M. R.; Johnson, D. S., Computers and Intractability: a guide to the theory of NP-completeness (1979), Freeman and Company: Freeman and Company San Francisco, CA · Zbl 0411.68039
[2] Carlier, J.; Pinson, E., An algorithm for solving the job-shop problem, Management Science, 35, 164-176 (1989) · Zbl 0677.90036
[3] Dell’Amico, M.; Trubian, M., Applying tabu search to the job shop scheduling problem, Annals of Operations Research, 41, 231-252 (1993) · Zbl 0771.90056
[4] Grabowski, J.; Wodecki, M., A very fast tabu search algorithm for the job shop problem, (Rego, C.; Alidaee, B., Metaheuristic optimization via memory and evolution (2004), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht) · Zbl 1072.90057
[5] Nowicki, E.; Smutnicki, C., A fast tabu search algorithm for the job shop problem, Management Science, 42, 797-813 (1996) · Zbl 0880.90079
[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] Croce, F. D.; Tadei, R.; Volta, G., A genetic algorithm for the job shop problem, Computers and Operations Research, 22, 15-24 (1995) · Zbl 0816.90081
[8] Schultz SR, Hodgson TJ, King RE. On solving the classic job shop makespan problem by minimizing Lmax. Raleigh, NC: Department of Industrial Engineering, North Carolina State University; 2004.; Schultz SR, Hodgson TJ, King RE. On solving the classic job shop makespan problem by minimizing Lmax. Raleigh, NC: Department of Industrial Engineering, North Carolina State University; 2004.
[9] Blazewicz, J.; Domschke, W.; Pesch, E., The job shop scheduling problem, 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] 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
[12] Balas, E.; Vazacopoulos, A., Guided local search with shifting bottleneck for job shop scheduling, Management Science, 44, 262-275 (1998) · Zbl 0989.90057
[13] Dorndorf, U.; Pesch, E., Evolution based learning in a job shop scheduling environment, Computers and Operations Research, 22, 25-40 (1995) · Zbl 0815.90089
[14] Pezzella, F.; Merelli, E., A tabu search method guided by shifting bottleneck for the job shop scheduling problem, European Journal of Operational Research, 120, 297-310 (2000) · Zbl 0953.90026
[15] Wang, L.; Zheng, D. Z., An effective optimization strategy for job shop scheduling problems, Computers and Operations Research, 28, 585-596 (2001) · Zbl 1017.90048
[16] Yamada, T.; Nakano, R., Job-shop scheduling by simulated annealing combined with deterministic local search, (Meta-heuristics: theory and applications (1996), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 237-248 · Zbl 0877.90047
[17] Adams, J.; Balas, E.; Zawack, D., The shifting bottleneck procedure for job shop scheduling, Management Science, 34, 391-401 (1988) · Zbl 0637.90051
[18] Aiex, R. M.; Binato, S.; Resende, M. G.C., Parallel GRASP with path-relinking for job shop scheduling, Parallel Computing, 29, 393-430 (2003)
[19] Dorigo M, Stützle T. Ant colony optimization. Cambridge, MA: MIT Press; 2004.; Dorigo M, Stützle T. Ant colony optimization. Cambridge, MA: MIT Press; 2004. · Zbl 1092.90066
[20] Dorigo, M.; Gambardella, L. M., Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1, 53-66 (1997)
[21] Bullnheimer, B.; Hartl, R. F.; Strauss, C., An improved ant system algorithm for the vehicle routing problem, Annals of Operations Research, 89, 319-328 (1999) · Zbl 0937.90125
[22] Bauer, A.; Bullnheimer, B.; Hartl, R. F.; Strauss, C., An ant colony optimization approach for the single machine total tardiness problem, (Proceedings of the 1999 congress on evolutionary computation (1999), IEEE Press: IEEE Press New York), 1445-1450
[23] den Besten M, Stützle T, Dorigo M. Ant colony optimization for the total weighted tardiness problem. In: Proceeding of PPSN VI, sixth international conference on parallel problem solving from nature. Lecture Notes in Computer Science 2000;1917:611-20.; den Besten M, Stützle T, Dorigo M. Ant colony optimization for the total weighted tardiness problem. In: Proceeding of PPSN VI, sixth international conference on parallel problem solving from nature. Lecture Notes in Computer Science 2000;1917:611-20.
[24] Gagné, C.; Price, W. L.; Gravel, M., Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times, Journal of the Operational Research Society, 53, 895-906 (2002) · Zbl 1130.90326
[25] Stützle, T., An ant approach for the flow shop problem, (Proceeding of EUFIT ‘98: sixth European congress on intelligent techniques and soft computing, vol. 3 (1998)), 1560-1564
[26] T’kindt, V.; Monmarché, N.; Tercinet, F.; Laügt, D., An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem, European Journal of Operational Research, 42, 250-257 (2002) · Zbl 1082.90592
[27] Colorni, A.; Dorigo, M.; Maniezzo, V.; Trubian, M., Ant system for job shop scheduling, Belgian Journal of Operations Research, 34, 39-53 (1994) · Zbl 0814.90047
[28] Blum, C.; Sampels, M., An ant colony optimization algorithm for shop scheduling problems, Journal of Mathematical Modelling and Algorithms, 3, 285-308 (2004) · Zbl 1146.90405
[29] Blum, C., Beam-ACO—hybridizing ant colony optimization with beam search: an application to open shop scheduling, Computers and Operations Research, 32, 1565-1591 (2005) · Zbl 1122.90427
[30] Blum C, Sampels M. Ant colony optimization for FOP shop scheduling: a case study on different pheromone representations. In: Proceedings of the 2002 congress on evolutionary computation (CEC’02), vol. 2. Los Alamitos, CA: IEEE Computer Society Press; 2002. p. 1558-63.; Blum C, Sampels M. Ant colony optimization for FOP shop scheduling: a case study on different pheromone representations. In: Proceedings of the 2002 congress on evolutionary computation (CEC’02), vol. 2. Los Alamitos, CA: IEEE Computer Society Press; 2002. p. 1558-63.
[31] Dorndorf, U.; Pesch, E.; Phan-Huy, T., Constraint propagation and problem decomposition: a preprocessing procedure for the job shop problem, Annals of Operations Research, 115, 125-145 (2002) · Zbl 1013.90057
[32] Dauzère-Pérès, S.; Lasserre, J. B., A modified shifting bottleneck procedure for job-shop scheduling, International Journal of Production Research, 31, 923-932 (1993) · Zbl 0773.90036
[33] Balas, E.; Lenstra, J. K.; Vazacopoulos, A., The one-machine problem with delayed precedence constraints and its use in job shop scheduling, Management Science, 41, 94-109 (1995) · Zbl 0824.90076
[34] Fleurent, C.; Glover, F., Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory, INFORMS Journal on Computing, 11, 198-204 (1991) · Zbl 1040.90541
[35] Binato, S.; Hery, W. J.; Loewenstern, D.; Resende, M. G.C., A GRASP for job shop scheduling, (Ribeiro, C. C.; Hansen, P., Essays and surveys on metaheuristics (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 59-79 · Zbl 1006.90040
[36] Blum, C., ACO applied to group shop scheduling: a case study on intensification and diversification, (Dorigo, M.; Di Caro, G.; Sampels, M., Proceedings of ANTS 2002—from ant colonies to artificial ants: third international workshop on ant algorithms, Lecture notes in computer science, vol. 2463 (2002), Springer: Springer Berlin, Germany), 14-27
[37] Glover, F., Tabu search (Part I), ORSA Journal on Computing, 1, 190-206 (1989) · Zbl 0753.90054
[38] Glover, F., Tabu search (Part II), ORSA Journal on Computing, 2, 4-32 (1990) · Zbl 0771.90084
[39] Lawrence S. Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (Supplement). Pittsburgh, PA: Graduate School of Industrial Administration, Carnegie Mellon University; 1984.; Lawrence S. Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (Supplement). Pittsburgh, PA: Graduate School of Industrial Administration, Carnegie Mellon University; 1984.
[40] Applegate, D.; Cook, W., A computational study of the job-shop scheduling problem, ORSA Journal on Computing, 3, 149-156 (1991) · Zbl 0755.90039
[41] Fisher, H.; Thompson, G. L., Probabilistic learning combinations of local job-shop scheduling rules, (Muth, J. M.; Thompson, G. L., Industrial scheduling (1963), Prentice-Hill: Prentice-Hill Englewood Cliffs, NJ, Chichester, UK)
[42] Taillard, É. D., Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 108-117 (1993) · Zbl 0769.90052
[43] Van Laarhoven, P. J.N.; Aarts, E. H.L.; Lenstra, J. K., Job shop scheduling by simulated annealing, Operations Research, 40, 113-125 (1992) · Zbl 0751.90039
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.