MPM Job-shop under Availability Constraints


  • Nozha Zribi í‰cole Centrale de Lille France
  • Luminița Duță State University "VALAHIA Tirgoviste", Romania
  • A. El Kamel


genetic algorithm, geometric approach, assignment heuristic


A large part of scheduling literature assumes that machines are available all the time. In this paper, the MPM Job-shop scheduling problem, where the machine maintenance has to be performed within certain time intervals inducing machine unavailability, is studied. Two approaches to solve the problem are proposed. The first is a two-phase approach where the assignment and the sequencing are solved separately. The second is an integrated approach based on the exact resolution of the 2-job problem using the geometric approach.


Adiri I., Bruno J., Frostig E., and Rinnooy Kan A. H. G. : Single machine flow-time with a single breakdown. Acta Informatica, 26, 679-696.

S.B. Akers et J. Friedman. - A non-numerical approach to production scheduling problems. Operations Research, vol. 3, 1955, pp. 3, 429-442.

Aggoune, R.: Ordonnancement d'Ateliers sous Contraintes de Disponibilité des Machines(2002) Ph.D. Thesis, Université de Metz, France.

Aggoune, R.: Two-job shop Scheduling Problems with availability Constraints. ICAPS 2004, June 3-7, 2004, Whistler, British Columbia, Canada.

Duta, L.: Contribution ´r l'étude de la conduite des systˇcmes de désassemblage.These (2006). Université de Franche-Comté Université de Bucarest.

Duta,L., Filip, F. G. Henrioud,J.-M. Popescu: Disassembly Line Scheduling with Genetic Algorithms. Int. J. of Computers, Communications & Control, ISSN 1841-9836, E-ISSN 1841-9844 Vol. III (2008), No. 3, pp. 270-280.

Filip F.G., Neagu G. and Donciulescu D. (1983). Job shop scheduling optimization in real time production control. Computers in Industry, 4(4) (North Holland, Amsterdam), 395 - 403.

Ruiz-Torres AJ., Nakatani K.: Application of real-time simulation to assign due dates on logisticmanufacturing networks. Proceedings of the 1998 Winter Simulation Conference.

Blazewicz J., Breit J., Formanowicz P., Kubiak W., Schmidt G.: Heuristic algorithms for the twomachine flowshop problem with limited machine availability. Omega Journal (2001), 29, 599-608.

Carlier J.: Scheduling jobs with release dates and tails on identical machines to minimize the makespan. European Journal of Operational research(1987), 29:298-306, North-Holland.

Carlier J.: The One-Machine Sequencing Problem, European Jounal of operational research(1982), 11: 42-47.

Jurisch B.: Scheduling Jobs in Shops with Multi Purpose Machines (1992) Ph.D Thesis, Universität Osnabrück.

J. Hurink, B. Jurisch et M. Thole. - Tabu search for the job-shop scheduling problem with multipurpose machines. Operations Research Spektrum, vol. 15, 1994, pp. 205-215.

Kubiak W., Blazewicz J., Formanowicz P., Breit J., Schmidt G.: Two-machine flow shops with lim-ited machine availability. European Journal of Opera-tional Research (2002) 136: 528-540.

Lee C.Y.: Machine scheduling with an availability constraint. Journal of Global Optimization(1996) 9: 395-416.

Glover F., Laguna M.: Tabu search, Kluwer Publish- ers, Boston 1997.

Jurisch, B., (1995). Lower bounds for the job-shop scheduling problem on multi-purpose machines. Discrete Applied Mathematics, 58, 145-156.

Lee C.Y.: Minimizing the mazkespan in two-machine flows-hop scheduling with availability constraint. Operations research letters (1997), 20: 129-139, .

Lee C.Y.: Two-machine flowshop scheduling with availability constraints. European Journal of Opera-tional Research (1999), 114: 420-429.

Lee KM., Yamakawa T.: A Genetic algorithm for general machine scheduling problems. Int.Conf. on Conventional and knowledge-Based Electronics Systems, Vol 2 pp60-66 Australia, 1998.

Mati, Y., and Xie, X.: Un algorithme polonimial pour le job shop flexible avec blocage : cas de deux jobs. Mosim'2003, April 23-25 april, Toulouse, France.

Mati, Y., and Xie, X.: The complexity of two-job shop problems with multi-purpose unrelated machines. European Journal of Operational Research, 152 (1), 159-169, 2004.

Nowicki E., Smutnicki C.: A Fast Taboo Search Algorithm for the Job-Shop Problem, Management Science (1996), Vol. 42, No. 6, pp. 797-813.

Schmidt G.: Scheduling on semi identical processors. Z. Oper.Res.1984, A28, 153-162, .

Schmidt G.: Scheduling independent tasks with deadlines on semi-identical processors. Journal of Operational research society, 39, 271-277, 1988.

Sanjay J., William J. Foley :Impact of Interruptions of Schedule Execution in Flexible Manufacturing Systems. The International Journal of Flexible Manufacturing Systems, 14, 319-344, 2002.

Roy B., Sussmann B.: Les probl'emes d'ordonnancement avec contraintes disjonctives (in French). Technical Report 9 bis, SEMA, Paris (France), December 1964.

Leon V. J., Wu S. D.: On scheduling with ready-times, due-dates and vacations. Naval Research Logistics, 39:53-65, 1992.;2-C

Schmidt G.: Scheduling with limited machine availability. European Journal of Operational Research (2000), 121, 1-15.

Mauguiere Ph., Billaut J-C., Bouquard J-L.: New single machine and job-shop scheduling problems with availability constraints. Journal of Scheduling, 2004.

Zribi N. : Ordonnancement des job-shop flexibles sous contraintes de disponibilité des machines. PHD Thesis, Ecole Centrale de Lille, France, 2005.



Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.