Lower bounds for the scheduling problem with uncertain demands

• Autorzy: Djamel Berkoune , Khaled Mesghouni , Besoa Rabenasolo
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

insertion; lower bounds; predicted demands; flexible job shop scheduling; makespan

• Wydawca: University of Zielona Gora Press
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2006
• Tom: 16
• Numer: 2
• Strony: 263-269

Daty

wydano

2006

otrzymano

2005-03-17

poprawiono

2006-02-02

(nieznana)

2006-04-10

Twórcy

autor

Djamel Berkoune

• LAGIS UMR CNRS 8146, Ecole Centrale de Lille, BP 48, 59651 Villeneuve d’Ascq Cedex, France

autor

Khaled Mesghouni

• LAGIS UMR CNRS 8146, Ecole Centrale de Lille, BP 48, 59651 Villeneuve d’Ascq Cedex, France

autor

Besoa Rabenasolo

• GEMTEX EA 2461, Ecole Nationale Superieure des Arts et Industries Textiles, 9 rue de l'Ermitage, BP 30329, 59056 Roubaix Cedex 01, France

Bibliografia

• Alvarez-Valdes R. and Tamarit J.M. (1987): Project scheduling with resource constraints: A branch and bound approach. - Europ. J. Oper. Res., Vol. 29, No. 3, pp. 262-273.
• 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.
• 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.
• 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).
• Billaut J.C., Carlier J. and Neron A. (2002): Ordonnancement d'ateliers à ressources multiples. Ordonnancement de la production. - Paris: Hermès.
• Brucker P. (2003): Scheduling Algorithms, 4-th Ed. - New York: Springer.
• Carlier J. (1982): The one machine sequencing problem. - Europ. J. Oper. Res., Vol. 11, No. 1, pp. 42-47.
• 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.
• Carlier J. and Chretienne P. (1988): Problème d'ordonnancement modélisation/complexité/algorithmes. - Paris: Masson.
• Carlier J. and Pinson E. (1989): An algorithm for solving the job shop problem. - Manag. Sci., Vol. 35, No. 2, pp. 164-176.
• 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.
• 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, Compiegne, France, pp. 8-25.
• Goldberg D.E. (1989): Genetic Algorithms in Search, Optimization and Machine Learning. - Reading, MA: Addison-Wesley.
• Holland J.H. (1992): Adaptation in Natural and Artificial Systems, 2-nd Ed. - Michigan: University Michigan MIT Press.
• 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.
• 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.
• 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.
• Mesghouni K. (1999): Application des algorithmes evolutionnistes dans les problèmes d'optimisation en ordonnancement de la production. - Ph.D. thesis, University of Lille 1, Lille, France.
• 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.
• 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.
• Pinedo M. (2002): Scheduling: Theory, Algorithm, and Systems, 2-nd Ed. - Upper Saddle River, NJ: Prentice Hall.
• 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-74.
• Renders J.M. (1995): Algorithmes Genetiques et Reseaux de Neurones. - Paris: Hermès.
• 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.
• Syswerda G. (1990): Schedule optimization using genetic algorithm, In: Handbook of Genetic Algorithms (L. Davis, Ed.). - New York: Van Nostrand Reinhold