×

A hybrid genetic algorithm for the job shop scheduling problem. (English) Zbl 1075.90028

Summary: This paper presents a hybrid genetic algorithm for the job shop scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a priority rule in which the priorities are defined by the genetic algorithm. Schedules are constructed using a procedure that generates parameterized active schedules. After a schedule is obtained a local search heuristic is applied to improve the solution. The approach is tested on a set of standard instances taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed algorithm.

MSC:

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

Software:

JOBSHOP
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Aarts, E. H.L.; Van Laarhoven, P. J.M.; Lenstra, J. K.; Ulder, N. L.J., A computational study of local search algorithms for job shop scheduling, ORSA Journal on Computing, 6, 118-125 (1994) · Zbl 0819.90040
[2] Aiex, R. M.; Binato, S.; Resende, M. G.C., Parallel GRASP with path-relinking for job shop scheduling, Parallel Computing, 29, 393-430 (2003)
[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] Applegate, D.; Cook, W., A computational study of the job-shop scheduling problem, ORSA Journal on Computing, 3, 149-156 (1991) · Zbl 0755.90039
[5] Bean, J. C., Genetics and random keys for sequencing and optimization, ORSA Journal on Computing, 6, 154-160 (1994) · Zbl 0807.90060
[6] Beasley, D., Bull, D.R., Martin, R.R., 1993. An overview of genetic algorithms: Part 1, Fundamentals, University Computing, Vol. 15, No. 2, pp. 58-69, Department of Computing Mathematics, University of Cardiff, UK; Beasley, D., Bull, D.R., Martin, R.R., 1993. An overview of genetic algorithms: Part 1, Fundamentals, University Computing, Vol. 15, No. 2, pp. 58-69, Department of Computing Mathematics, University of Cardiff, UK
[7] Binato, S.; Hery, W. J.; Loewenstern, D. M.; Resende, M. G.C., A GRASP for job shop scheduling, (Ribeiro, C. C.; Hansen, P., Essays and Surveys in Metaheuristics (2002), Kluwer Academic Publishers) · Zbl 1006.90040
[8] 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
[9] Carlier, J.; Pinson, E., An algorithm for solving the job shop problem, Management Science, 35, 29, 164-176 (1989) · Zbl 0677.90036
[10] Carlier, J.; Pinson, E., A practical use of Jackson’s preemptive schedule for solving the job-shop problem, Annals of Operations Research, 26, 269-287 (1990) · Zbl 0709.90061
[11] Cheng, R.; Gen, M.; Tsujimura, Y., A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: Hybrid genetic search strategies, Computers & Industrial Engineering, 36, 343-364 (1999)
[12] Croce, F.; Tadei, R.; Volta, G., A genetic algorithm for the job shop problem, Computers and Operations Research, 22, 1, 15-24 (1995) · Zbl 0816.90081
[13] Davis, L., Job shop scheduling with genetic algorithms, (Proceedings of the First International Conference on Genetic Algorithms and their Applications (1985), Morgan Kaufmann), 136-140
[14] Dorndorf, U.; Pesch, E., Evolution based learning in a job shop environment, Computers and Operations Research, 22, 25-40 (1995) · Zbl 0815.90089
[15] Fisher, H.; Thompson, G. L., Probabilistic learning combinations of local job-shop scheduling rules, (Muth, J. F.; Thompson, G. L., Industrial Scheduling (1963), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ), 225-251
[16] French, S., Sequencing and scheduling-An introduction to the mathematics of the job-shop (1982), Ellis Horwood, John Wiley & Sons: Ellis Horwood, John Wiley & Sons New York · Zbl 0479.90037
[17] Giffler, B.; Thompson, G. L., Algorithms for solving production scheduling problems, Operations Research, 8, 4, 487-503 (1960) · Zbl 0248.90022
[18] Goldberg, D. E., Genetic Algorithms in Search Optimization and Machine Learning (1989), Addison-Wesley · Zbl 0721.68056
[19] Gonçalves, J. F.; Beirão, N. C., Um Algoritmo Genético Baseado em Chaves Aleatórias para Sequenciamento de Operações, Revista Associação Portuguesa de Desenvolvimento e Investigação Operacional, 19, 123-137 (1999), (in Portuguese)
[20] Gonçalves, J.F., Mendes, J.M., 1994. A look-ahead dispatching rule for scheduling operations. VII Latin-Ibero-American Conference on Operations Research and Systems Engineering, University of Chile, Santiago, Chile; Gonçalves, J.F., Mendes, J.M., 1994. A look-ahead dispatching rule for scheduling operations. VII Latin-Ibero-American Conference on Operations Research and Systems Engineering, University of Chile, Santiago, Chile
[21] Gray, C.; Hoesada, M., Matching heuristic scheduling rules for job shops to the business sales level, Production and Inventory Management Journal, 4, 12-17 (1991)
[22] Jain, A. S.; Meeran, S., A state-of-the-art review of job-shop scheduling techniques, European Journal of Operational Research, 113, 390-434 (1999) · Zbl 0938.90028
[23] Laarhoven, P. J.M. V.; Aarts, E. H.L.; Lenstra, J. K., Job shop scheduling by simulated annealing, Operations Research, 40, 113-125 (1992) · Zbl 0751.90039
[24] Lageweg, B. J.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Job shop scheduling by implicit enumeration, Management Science, 24, 441-450 (1977) · Zbl 0373.90034
[25] Lawrence, S., 1984. Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques, GSIA, Carnegie Mellon University, Pittsburgh, PA; Lawrence, S., 1984. Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques, GSIA, Carnegie Mellon University, Pittsburgh, PA
[26] Lenstra, J. K.; Rinnooy Kan, A. H.G., Computational complexity of discrete optimisation problems, Annals of Discrete Mathematics, 4, 121-140 (1979) · Zbl 0411.68042
[27] Lourenço, H. R., Local optimization and the job-shop scheduling problem, European Journal of Operational Research, 83, 347-364 (1995) · Zbl 0904.90089
[28] Lourenço, H. R.; Zwijnenburg, M., Combining the large-step optimization with tabu-search: Application to the job-shop scheduling problem, (Osman, I. H.; Kelly, J. P., Metaheuristics: Theory and Applications (1996), Kluwer Academic Publishers), 219-236 · Zbl 0877.90045
[29] Nowicki, E.; Smutnicki, C., A fast taboo search algorithm for the job-shop problem, Management Science, 42, 6, 797-813 (1996) · Zbl 0880.90079
[30] Oliveira, J.A.V., 2000. Aplicação de Modelos e Algoritmos de Investigação Operacional ao Planeamento de Operações em Armaz’ens. Ph.D. Thesis, Universidade do Minho, Portugal (in Portuguese); Oliveira, J.A.V., 2000. Aplicação de Modelos e Algoritmos de Investigação Operacional ao Planeamento de Operações em Armaz’ens. Ph.D. Thesis, Universidade do Minho, Portugal (in Portuguese)
[31] Pinson, E., The job shop scheduling problem: A concise survey and some recent developments, (Chrëtienne, P.; Coffman, E. G.; Lenstra, J. K.; Liu, Z., Scheduling Theory and its Application (1995), John Wiley and Sons), 277-293
[32] Roy, B., Sussmann, 1964. Les Problèes d’ ordonnancement avec contraintes dijonctives, Note DS 9 bis, SEMA, Montrouge; Roy, B., Sussmann, 1964. Les Problèes d’ ordonnancement avec contraintes dijonctives, Note DS 9 bis, SEMA, Montrouge
[33] Sabuncuoglu, I.; Bayiz, M., Job shop scheduling with beam search, European Journal of Operational Research, 118, 390-412 (1999) · Zbl 0940.90037
[34] Spears, W.M., Dejong, K.A., 1991. On the virtues of parameterized uniform crossover. In: Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 230-236; Spears, W.M., Dejong, K.A., 1991. On the virtues of parameterized uniform crossover. In: Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 230-236
[35] Storer, R.H., Wu, S.D., Park, I., 1992. Genetic algorithms in problem space for sequencing problems. In: Proceedings of a Joint US-German Conference on Operations Research in Production Planning and Control, pp. 584-597; Storer, R.H., Wu, S.D., Park, I., 1992. Genetic algorithms in problem space for sequencing problems. In: Proceedings of a Joint US-German Conference on Operations Research in Production Planning and Control, pp. 584-597
[36] Taillard, E. D., Parallel taboo search techniques for the job shop scheduling problem, ORSA Journal on Computing, 6, 2, 108-117 (1994) · Zbl 0807.90066
[37] Vaessens, R. J.M.; Aarts, E. H.L.; Lenstra, J. K., Job shop scheduling by local search, INFORMS Journal (1996) · Zbl 0863.90094
[38] Wang, L.; Zheng, D., An effective hybrid optimisation strategy for job-shop scheduling problems, Computers & Operations Research, 28, 585-596 (2001) · Zbl 1017.90048
[39] Williamson, D. P.; Hall, L. A.; Hoogeveen, J. A.; Hurkens, C. A.J.; Lenstra, J. K.; Sevast’janov, S. V.; Shmoys, D. B., Short shop schedules, Operations Research, 45, 2, 288-294 (1997) · Zbl 0890.90112
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.