Lower bounds for the scheduling problem with uncertain demands

Berkoune, D. ; Mesghouni, K. ; Rabenasolo, B.

International Journal of Applied Mathematics and Computer Science, Tome 16 (2006) no. 2, pp. 263-269.

Résumé

This paper proposes various lower bounds to the makespan of the flexible job shop scheduling problem (FJSP). The FJSP is known in the literature as one of the most difficult combinatorial optimisation problems (NP-hard). We will use genetic algorithms for the optimisation of this type of problems. The list of the demands is divided in two sets: the actual demand, which is considered as certain (a list of jobs with known characteristics), and the predicted demand, which is a list of uncertain jobs. The actual demand is scheduled in priority by the genetic algorithm. Then, the predicted demand is inserted using various methods in order to generate different scheduling solutions. Two lower bounds are given for the makespan before and after the insertion of the predicted demand. The performance of solutions is evaluated by comparing the real values obtained on many static and dynamic scheduling examples with the corresponding lower bounds.

Détail

Keywords: flexible job shop scheduling, insertion, makespan, predicted demands, lower bounds
Mots-clés : szeregowanie zadań, prognozowanie popytu, granica dolna

Bibliographie

[1] Alvarez-Valdes R. and Tamarit J.M. (1987): Project scheduling with resource constraints: A branch bound approach. - Europ. J. Oper. Res., Vol. 29, No. 3, pp. 262-273.

[2] Artigues C. (1997): Ordonnancement en temps réel d'ateliers avec temps de préparation des ressources. -Ph.D. thesis, University of Paul Sabatier, Toulouse, France.

[3] Artigues C., Michelon P. and Reusser S. (2003): Insertion techniques for static and dynamic resource constrained project scheduling. - Europ. J. Oper. Res., Vol. 149, No. 2, pp. 249-267.

[4] Berkoune D., Mesghouni K. and Rabenasolo B. (2004): Insertion methods of uncertain demands in workshop scheduling. - Proc. 4-th Conf. AUTEX, Roubaix, France, (on CD-ROM).

[5] Billaut J.C., Carlier J. and Néron A. (2002): Ordonnancement d'ateliers à ressources multiples. Ordonnancement de la production. -Paris: Hermès.

[6] Brucker P. (2003): Scheduling Algorithms, 4-th Ed. - New York: Springer.

[7] Carlier J. (1982): The one machine sequencing problem. - Europ. J. Oper. Res., Vol. 11, No. 1, pp. 42-47.

[8] Carlier J. (1987): Scheduling jobs with release dates and tails on identical machines to minimize makespan. - Europ. J. Oper. Res., Vol. 29, No. 3, pp. 298-306.

[9] Carlier J. and Chrétienne P. (1988): Problème d'ordonnancement modélisation/complexité/algorithmes. - Paris: Masson.

[10] Carlier J. and Pinson E. (1989): An algorithm for solving the job shop problem.-Manag. Sci., Vol. 35, No. 2, pp. 164-176.

[11] Della Croce F., Tadei R. and Volta G. (1995): A genetic algorithm for job shop problem. - Comput. Oper. Res., Vol. 22, No. 1, pp. 15-24.

[12] Demeulemeester E. and Herroleln W. (1990): A branch and bound procedure for the multiple constrained resource project scheduling problem. - Proc. 2-nd Int. Workshop Project Management and Scheduling, Compiègne, France, pp. 8-25.

[13] Goldberg D.E. (1989): Genetic Algorithms in Search, Optimization and Machine Learning. - Reading, MA: Addison- Wesley.

[14] Holland J.H. (1992): Adaptation in Natural and Artificial Systems, 2-nd Ed. - Michigan: University Michigan MIT Press.

[15] Kacem I. (2003): Ordonnancement multicritères des job shops flexibles: Formulation, bornes inférieures et approche évolutionniste coopérative. - Ph.D. thesis, University of Lille 1, Lille, France.

[16] Kobayashi S., Ono I. and Yamamura M. (1995): An efficient genetic algorithm for job shop scheduling problem. - Proc. ICGA'95, San Francisco, CA, USA, pp. 506-511.

[17] Mattfeld D.C. and Bierwirth C. (2004): An efficient genetic algorithm for job shop scheduling with tardiness objectives. - Europ. J. Oper. Res., Vol. 155, No. 3, pp. 616-630.

[18] Mesghouni K. (1999): Application des algorithmes évolutionnistes dans les problèmes d'optimisation en ordonnancement de la production. - Ph.D. thesis, University of Lille 1, Lille, France.

[19] Mesghouni K. and Rabenasolo B. (2002): Multi-period predictive production scheduling with uncertain demands. - Proc. IEEE Int. Conf. Systems, Man and Cybernetics, SMC'02, Hammamet, Tunisia, Vol. 6, Paper WA2K2, p. 6.

[20] Mesghouni K., Hammadi S. and Borne P. (2004): Evolutionary algorithm for job shop scheduling. - Int. J. Appl. Math. Comput. Sci., Vol. 14, No. 1, pp. 91-103.

[21] Pinedo M. (2002): Scheduling: Theory, Algorithm, and Systems, 2-nd Ed.- Upper Saddle River, NJ: Prentice Hall.

[22] Ponnambalam S.G., Aravindan P. and Sreenivasa Rao P. (2001): Comparative evaluation of genetic algorithms for job shop scheduling.-Prod. Plann. Contr., Vol. 12, No. 6, pp. 560-574.

[23] Renders J.M. (1995): Algorithmes Génétiques et Réseaux de Neurones. -Paris: Hermès.

[24] Sevaux M. and Dauzère-Pérès S. (2003): Genetic algorithms to minimize the weighted number of late jobs on a single machine. - Europ. J. Oper. Res., Vol. 151, No. 2, pp. 296-306.

[25] Syswerda G. (1990): Schedule optimization using genetic algorithm, In: Handbook of Genetic Algorithms (L. Davis, Ed.).-New York: Van Nostrand Reinhold.