MPM Job-shop under Availability Constraints

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


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.


[1] 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.

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

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

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

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

[6] 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.

[7] 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.

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

[9] 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.

[10] 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.

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

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

[13] 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.

[14] 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.

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

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

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

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

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

[20] 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.

[21] 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.

[22] 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.

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

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

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

[26] 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.

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

[28] Leon V. J., Wu S. D.: On scheduling with ready-times, due-dates and vacations. Naval Research Logistics, 39:53-65, 1992.<53::AID-NAV3220390105>3.0.CO;2-C

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

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

[31] Zribi N. : Ordonnancement des job-shop flexibles sous contraintes de disponibilité des machines. PHD Thesis, Ecole Centrale de Lille, France, 2005.
How to Cite
ZRIBI, Nozha; DUȚĂ, Luminița; KAMEL, A. El. MPM Job-shop under Availability Constraints. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 4, n. 4, p. 439-451, dec. 2009. ISSN 1841-9844. Available at: <>. Date accessed: 23 jan. 2021. doi:


genetic algorithm, geometric approach, assignment heuristic