Evolutionary algorithms for job-shop scheduling

Khaled Mesghouni; Slim Hammadi; Pierre Borne

International Journal of Applied Mathematics and Computer Science (2004)

  • Volume: 14, Issue: 1, page 91-103
  • ISSN: 1641-876X

Abstract

top
This paper explains how to use Evolutionary Algorithms (EA) to deal with a flexible job shop scheduling problem, especially minimizing the makespan. The Job-shop Scheduling Problem (JSP) is one of the most difficult problems, as it is classified as an NP-complete one (Carlier and Chretienne, 1988; Garey and Johnson, 1979). In many cases, the combination of goals and resources exponentially increases the search space, and thus the generation of consistently good scheduling is particularly difficult because we have a very large combinatorial search space and precedence constraints between operations. Exact methods such as the branch and bound method and dynamic programming take considerable computing time if an optimum solution exists. In order to overcome this difficulty, it is more sensible to obtain a good solution near the optimal one. Stochastic search techniques such as evolutionary algorithms can be used to find a good solution. They have been successfully used in combinatorial optimization, e.g. in wire routing, transportation problems, scheduling problems, etc. (Banzhaf et al., 1998; Dasgupta and Michalewicz, 1997). Our objective is to establish a practical relationship between the development in the EA area and the reality of a production JSP by developing, on the one hand, two effective genetic encodings, such as parallel job and parallel machine representations of the chromosome, and on the other, genetic operators associated with these representations. In this article we deal with the problem of flexible job-shop scheduling which presents two difficulties: the first is the assignment of each operation to a machine, and the other is the scheduling of this set of operations in order to minimize our criterion (e.g. the makespan).

How to cite

top

Mesghouni, Khaled, Hammadi, Slim, and Borne, Pierre. "Evolutionary algorithms for job-shop scheduling." International Journal of Applied Mathematics and Computer Science 14.1 (2004): 91-103. <http://eudml.org/doc/207683>.

@article{Mesghouni2004,
abstract = {This paper explains how to use Evolutionary Algorithms (EA) to deal with a flexible job shop scheduling problem, especially minimizing the makespan. The Job-shop Scheduling Problem (JSP) is one of the most difficult problems, as it is classified as an NP-complete one (Carlier and Chretienne, 1988; Garey and Johnson, 1979). In many cases, the combination of goals and resources exponentially increases the search space, and thus the generation of consistently good scheduling is particularly difficult because we have a very large combinatorial search space and precedence constraints between operations. Exact methods such as the branch and bound method and dynamic programming take considerable computing time if an optimum solution exists. In order to overcome this difficulty, it is more sensible to obtain a good solution near the optimal one. Stochastic search techniques such as evolutionary algorithms can be used to find a good solution. They have been successfully used in combinatorial optimization, e.g. in wire routing, transportation problems, scheduling problems, etc. (Banzhaf et al., 1998; Dasgupta and Michalewicz, 1997). Our objective is to establish a practical relationship between the development in the EA area and the reality of a production JSP by developing, on the one hand, two effective genetic encodings, such as parallel job and parallel machine representations of the chromosome, and on the other, genetic operators associated with these representations. In this article we deal with the problem of flexible job-shop scheduling which presents two difficulties: the first is the assignment of each operation to a machine, and the other is the scheduling of this set of operations in order to minimize our criterion (e.g. the makespan).},
author = {Mesghouni, Khaled, Hammadi, Slim, Borne, Pierre},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {job-shop scheduling; evolutionary algorithms; parallel representation},
language = {eng},
number = {1},
pages = {91-103},
title = {Evolutionary algorithms for job-shop scheduling},
url = {http://eudml.org/doc/207683},
volume = {14},
year = {2004},
}

TY - JOUR
AU - Mesghouni, Khaled
AU - Hammadi, Slim
AU - Borne, Pierre
TI - Evolutionary algorithms for job-shop scheduling
JO - International Journal of Applied Mathematics and Computer Science
PY - 2004
VL - 14
IS - 1
SP - 91
EP - 103
AB - This paper explains how to use Evolutionary Algorithms (EA) to deal with a flexible job shop scheduling problem, especially minimizing the makespan. The Job-shop Scheduling Problem (JSP) is one of the most difficult problems, as it is classified as an NP-complete one (Carlier and Chretienne, 1988; Garey and Johnson, 1979). In many cases, the combination of goals and resources exponentially increases the search space, and thus the generation of consistently good scheduling is particularly difficult because we have a very large combinatorial search space and precedence constraints between operations. Exact methods such as the branch and bound method and dynamic programming take considerable computing time if an optimum solution exists. In order to overcome this difficulty, it is more sensible to obtain a good solution near the optimal one. Stochastic search techniques such as evolutionary algorithms can be used to find a good solution. They have been successfully used in combinatorial optimization, e.g. in wire routing, transportation problems, scheduling problems, etc. (Banzhaf et al., 1998; Dasgupta and Michalewicz, 1997). Our objective is to establish a practical relationship between the development in the EA area and the reality of a production JSP by developing, on the one hand, two effective genetic encodings, such as parallel job and parallel machine representations of the chromosome, and on the other, genetic operators associated with these representations. In this article we deal with the problem of flexible job-shop scheduling which presents two difficulties: the first is the assignment of each operation to a machine, and the other is the scheduling of this set of operations in order to minimize our criterion (e.g. the makespan).
LA - eng
KW - job-shop scheduling; evolutionary algorithms; parallel representation
UR - http://eudml.org/doc/207683
ER -

References

top
  1. Baghi S., Uckun S., Miyab Y. and Kawamura K. (1991): Exploring problem-specific recombination operators for job shop scheduling. - Proc. 4-th Int. Conf. Genetic Algorithms, University of California, San Diego, pp. 10-17, July 13-16. 
  2. Banzhaf W., Nordin P., Keller R.E. and Francone F.D. (1998): Genetic Programming: An Introduction on the Automatic Evolution of Computer Programs and Its Application. - San Francisco: Morgan Kaufmann. Zbl0893.68117
  3. Bruns R. (1993): Direct chromosome representation and advanced genetic operators for production scheduling. - Proc. 5-th Int. Conf. Genetic Algorithms, University of Illinois at Urbana-Champaign, pp. 352-359. 
  4. Carlier J. and Chretienne P. (1988): Problèmes d'ordonnancement: Modelisation complexite algorithmes. - Paris: Masson. 
  5. Croce F., Tadei R. and Volta G. (1995): A genetic algorithm for the job shop problem. - Comp. Opers. Res., Vol. 22, No. 1, pp. 15-24. Zbl0816.90081
  6. Dasgupta D. and Michalewicz Z. (1997): Evolutionary Algorithms in Engineering Applications. - Berlin: Springer-Verlag. Zbl0879.68043
  7. Della Croce F., Tadei R. and Volta G. (1995): A Genetic Algorithm for Job Shop Problem. - Comput. Ops. Res., Vol. 22, No. 1, pp. 15-24. Zbl0816.90081
  8. Fonseca C.M. and Fleming P.J. (1998): Multiobjective optimization and multiple constraint handling with evolutionary algorithms, Part I: Unified formulation. - IEEE TransSMC, Part A: Syst. Hum., Vol. 28, No. 1, pp. 26-37. 
  9. Garey M.R. and Johnson D.S. (1979): Computers and Intractability: A Guide to Theory of NP-Completeness. - New York: W.H. Freeman and Co. Zbl0411.68039
  10. Goldberg D.E. (1989): Genetic Algorithms in Search, Optimization, and Machine Learning. - Massachusetts: Addison Wesley. Zbl0721.68056
  11. Golver F., Taillard E., De Werra D. (1993): A user's guide to tabu search. - Ann. Opers. Res., Vol. 41, No. 1, pp. 3-28. Zbl0772.90063
  12. Kirkpatrick S., Gelatt C.D. and Vecchi M.P. (1983): Optimization by simulated annealing. - Science, Vol. 220, No. 4598, pp. 671-680. Zbl1225.90162
  13. Mesghouni K., Hammadi S. and Borne P. (1998): On modeling genetic algorithm for flexible job-shop scheduling problem. - Stud. Inform. Contr. J., Vol. 7, No. 1, pp. 37-47. 
  14. Mesghouni K. (1999): Application des algorithmes evolutionnistes dans les problemes d'optimisation en ordonnancement de la production. - Ph.D. Thesis, Lille 1 University, France. 
  15. Mesghouni K., Pesin P., Trentesaux D., Hammadi S., Tahon C. and Borne P.(1999): Hybrid approach to decision making for job-shop scheduling. - Prod. Plann. Contr. J., Vol. 10, No. 7, pp. 690-706. 
  16. Michalewicz Z. (1992): Genetic Algorithms + Data Structures = Evolution Programs. - Berlin: Springer. Zbl0763.68054
  17. Portman C.M. (1996): Genetic algorithms and scheduling: A state of the art and some proposition. - Proc. Workshop Production Planning and Control, Mons, Belgium, pp. i-xxiv. 
  18. Quagliarella D., Periaux J., Poloni C. and Winter G. (1998): Genetic Algorithms and Evolution Strategies in Engineering and Computer Sciences. -England: John Whiley. Zbl0889.68005
  19. Syswerda G. (1990): Schedule optimization using genetic algorithm, In: Handbook of Genetic Algorithm. - pp. 323-349, New York: Van Nostrand Reinhold. 
  20. Uckun S., Baghi S. and Kawamura K. (1993): Managing genetic search in job-shop scheduling. - IEEE Expert, Vol. 8, No. 5, pp. 15-24. 

Citations in EuDML Documents

top
  1. Djamel Berkoune, Khaled Mesghouni, Besoa Rabenasolo, Lower bounds for the scheduling problem with uncertain demands
  2. Horacio González-Vélez, Maryam Kontagora, Performance evaluation of MapReduce using full virtualisation on a departmental cloud
  3. Joanna Kołodziej, Fatos Xhafa, Modern approaches to modeling user requirements on resource and task allocation in hierarchical computational grids
  4. Robert Schaefer, Aleksander Byrski, Maciej Smołka, The island model as a Markov dynamic system
  5. Marlene Arangú, Miguel A. Salido, A fine-grained arc-consistency algorithm for non-normalized constraint satisfaction problems
  6. Rafał Szłapczyński, Joanna Szłapczyńska, Customized crossover in evolutionary sets of safe ship trajectories

NotesEmbed ?

top

You must be logged in to post comments.