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.
@article{bwmeta1.element.bwnjournal-article-amcv16i2p263bwm,
author = {Berkoune, Djamel and Mesghouni, Khaled and Rabenasolo, Besoa},
title = {Lower bounds for the scheduling problem with uncertain demands},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {16},
year = {2006},
pages = {263-269},
zbl = {1151.90395},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv16i2p263bwm}
}
Berkoune, Djamel; Mesghouni, Khaled; Rabenasolo, Besoa. Lower bounds for the scheduling problem with uncertain demands. International Journal of Applied Mathematics and Computer Science, Tome 16 (2006) pp. 263-269. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv16i2p263bwm/
[000] 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. | Zbl 0614.90056
[001] 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.
[002] 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. | Zbl 1040.90013
[003] 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). | Zbl 1151.90395
[004] Billaut J.C., Carlier J. and Neron A. (2002): Ordonnancement d'ateliers à ressources multiples. Ordonnancement de la production. - Paris: Hermès.
[005] Brucker P. (2003): Scheduling Algorithms, 4-th Ed. - New York: Springer.
[006] Carlier J. (1982): The one machine sequencing problem. - Europ. J. Oper. Res., Vol. 11, No. 1, pp. 42-47. | Zbl 0482.90045
[007] 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. | Zbl 0622.90049
[008] Carlier J. and Chretienne P. (1988): Problème d'ordonnancement modélisation/complexité/algorithmes. - Paris: Masson.
[009] Carlier J. and Pinson E. (1989): An algorithm for solving the job shop problem. - Manag. Sci., Vol. 35, No. 2, pp. 164-176. | Zbl 0677.90036
[010] 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. | Zbl 0816.90081
[011] 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.
[012] Goldberg D.E. (1989): Genetic Algorithms in Search, Optimization and Machine Learning. - Reading, MA: Addison-Wesley. | Zbl 0721.68056
[013] Holland J.H. (1992): Adaptation in Natural and Artificial Systems, 2-nd Ed. - Michigan: University Michigan MIT Press.
[014] 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.
[015] 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.
[016] 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. | Zbl 1044.90035
[017] 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.
[018] 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.
[019] 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. | Zbl 1171.90402
[020] Pinedo M. (2002): Scheduling: Theory, Algorithm, and Systems, 2-nd Ed. - Upper Saddle River, NJ: Prentice Hall.
[021] 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.
[022] Renders J.M. (1995): Algorithmes Genetiques et Reseaux de Neurones. - Paris: Hermès.
[023] 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. | Zbl 1053.90046
[024] Syswerda G. (1990): Schedule optimization using genetic algorithm, In: Handbook of Genetic Algorithms (L. Davis, Ed.). - New York: Van Nostrand Reinhold