Lower bounds for the scheduling problem with uncertain demands

Djamel Berkoune; Khaled Mesghouni; Besoa Rabenasolo

International Journal of Applied Mathematics and Computer Science (2006)

  • Volume: 16, Issue: 2, page 263-269
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Berkoune, Djamel, Mesghouni, Khaled, and Rabenasolo, Besoa. "Lower bounds for the scheduling problem with uncertain demands." International Journal of Applied Mathematics and Computer Science 16.2 (2006): 263-269. <http://eudml.org/doc/207791>.

@article{Berkoune2006,
abstract = {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.},
author = {Berkoune, Djamel, Mesghouni, Khaled, Rabenasolo, Besoa},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {insertion; lower bounds; predicted demands; flexible job shop scheduling; makespan},
language = {eng},
number = {2},
pages = {263-269},
title = {Lower bounds for the scheduling problem with uncertain demands},
url = {http://eudml.org/doc/207791},
volume = {16},
year = {2006},
}

TY - JOUR
AU - Berkoune, Djamel
AU - Mesghouni, Khaled
AU - Rabenasolo, Besoa
TI - Lower bounds for the scheduling problem with uncertain demands
JO - International Journal of Applied Mathematics and Computer Science
PY - 2006
VL - 16
IS - 2
SP - 263
EP - 269
AB - 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.
LA - eng
KW - insertion; lower bounds; predicted demands; flexible job shop scheduling; makespan
UR - http://eudml.org/doc/207791
ER -

References

top
  1. 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. Zbl0614.90056
  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. Zbl1040.90013
  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). Zbl1151.90395
  5. Billaut J.C., Carlier J. and Neron 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. Zbl0482.90045
  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. Zbl0622.90049
  9. Carlier J. and Chretienne 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. Zbl0677.90036
  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. Zbl0816.90081
  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, Compiegne, France, pp. 8-25. 
  13. Goldberg D.E. (1989): Genetic Algorithms in Search, Optimization and Machine Learning. - Reading, MA: Addison-Wesley. Zbl0721.68056
  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. Zbl1044.90035
  18. 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. 
  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. Zbl1171.90402
  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-74. 
  23. Renders J.M. (1995): Algorithmes Genetiques et Reseaux 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. Zbl1053.90046
  25. Syswerda G. (1990): Schedule optimization using genetic algorithm, In: Handbook of Genetic Algorithms (L. Davis, Ed.). - New York: Van Nostrand Reinhold 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.