A genetic algorithm for the job shop problem. (English) Zbl 0816.90081

Della Croce, Federico; Tadei, Roberto; Volta, Giuseppe

Comput. Oper. Res. 22, No. 1, 15-24 (1995).

Summary: We introduce a genetic algorithm whose peculiarities are the introduction of an encoding based on preference rules and an updating step which speeds up the evolutionary process. This method improves on the results gained previously with genetic algorithms and has shown itself to be competitive with other heuristics. The same algorithm has been applied to flow shop problems, revealing itself to be considerably more effective than branch and bound techniques.

MSC:

90B35	Deterministic scheduling theory in operations research
68T05	Learning and adaptive systems in artificial intelligence
92D10	Genetics and epigenetics

Keywords:

job shop scheduling; genetic algorithm; flow shop

Software:

JOBSHOP

References:

[1]	Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., Sequencing and scheduling: algorithms and complexity, (Report BS-R8909 (1989), Department of Operations Research, Statistic, and System Theory, Centre for Mathematics and Computer Science: Department of Operations Research, Statistic, and System Theory, Centre for Mathematics and Computer Science Amsterdam) · Zbl 0482.68035
[2]	Garey, M. R.; Johnson, D. S.; Sethi, R., The complexity of flowshop and job-shop scheduling, Math. Opl Res., 1, 117-129 (1976) · Zbl 0396.90041
[3]	Muth, J. F.; Thompson, G. L., Industrial Scheduling (1963), Prentice Hall: Prentice Hall Englewood Cliffs, N.J
[4]	Nakano, R.; Yamada, T., Conventional genetic algorithm for job shop scheduling, (Proceedings of the Fourth International Conference on Genetic Algorithms and Their Application (1991))
[5]	Falkenauer, E.; Bouffoix, S., A genetic algorithm for job shop, (Proceedings of the 1991 IEEE International Conference on Robotics and Automation (1991))
[6]	Van Laarhoven, P. J.M.; Aarts, E. H.L.; Lenstra, J. K., Job shop scheduling by simulated annealing, Opns Res., 40, 113-125 (1992) · Zbl 0751.90039
[7]	Dell’Amico, M.; Trubian, M., Applying tabu search to the job shop scheduling problem, Ann. Ops Res., 41, 231-252 (1993) · Zbl 0771.90056
[8]	Holland, J. H., Adaption in Natural and Artificial Systems (1975), The University of Michigan Press: The University of Michigan Press Ann Arbor · Zbl 0317.68006
[9]	Dorigo, M., Genetic Algorithms: the state-of-the-art and some research proposals, (Report No. 89-058 (1989), Dilartimento di Elettronica, Politecnico di Milano)
[10]	De Jong, K. A., An analysis of the behaviour of a class of genetic adaptive systems, (Ph.D. dissertation (1975), University of Michigan)
[11]	Davis, L., (Handbook of Genetic Algorithms (1991), Van Nostrand Reinhold: Van Nostrand Reinhold Amsterdam)
[12]	Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning (1989), Addison Wesley: Addison Wesley New York · Zbl 0721.68056
[13]	Goldberg, D. E.; Lingle, R., Alleles, loci and the traveling salesman problem, (Proceedings of an International Conference on Genetic Algorithms and Their Application (1985)) · Zbl 0674.90095
[14]	French, S., Sequencing and Scheduling (1982), Ellis Horwood: Ellis Horwood Chichester
[15]	Syswerda, G., Uniform Crossover in genetic algorithms, (Proceedings of the Third International Conference on Genetic Algorithms and Their Applications (1989))
[16]	Adams, J.; Balas, E.; Zawack, D., The shifting bottleneck procedure for job shop scheduling, Mgmt Sci., 34, 391-401 (1988) · Zbl 0637.90051
[17]	Lawrence, S., Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (1984), GSIA, Carnegie Mellon University
[18]	Applegate, D.; Cook, W., A computational study of the job shop scheduling problem, ORSA J. Comput., 3, 149-156 (1991) · Zbl 0755.90039