Scheduling jobs in open shops with limited machine availability
RAIRO - Operations Research - Recherche Opérationnelle, Tome 36 (2002) no. 2, pp. 149-156.

In this paper, open shop scheduling problems with limited machine availability are studied. Such a limited availability of machines may appear in many real-life situations, e.g. as preventive maintenance activities. Three types of jobs are distinguished: non-preemptable, resumable and preemptable. An operation of a resumable job if not completed before a non-availability period of a machine may be suspended and continued without additional cost when the machine becomes available. In the paper, results are given for the scheduling problems associated with the three types of jobs. For preemptable jobs polynomial-time algorithms based on the two-phase method are proposed.

DOI : https://doi.org/10.1051/ro:2002008
Mots clés : limited machine availability, computational complexity, two-phase method, mathematical programming
@article{RO_2002__36_2_149_0,
     author = {B{\l}a\.zewicz, Jacek and Formanowicz, Piotr},
     title = {Scheduling jobs in open shops with limited machine availability},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {149--156},
     publisher = {EDP-Sciences},
     volume = {36},
     number = {2},
     year = {2002},
     doi = {10.1051/ro:2002008},
     zbl = {1062.90024},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro:2002008/}
}
Błażewicz, Jacek; Formanowicz, Piotr. Scheduling jobs in open shops with limited machine availability. RAIRO - Operations Research - Recherche Opérationnelle, Tome 36 (2002) no. 2, pp. 149-156. doi : 10.1051/ro:2002008. http://www.numdam.org/articles/10.1051/ro:2002008/

[1] J. Błażewicz, J. Breit, P. Formanowicz, W. Kubiak and G. Schmidt, Heuristic algorithms for the two-machine flowshop with limited machine availability. Omega - International J. Management Sci. 29 (2001) 599-608.

[2] J. Błażewicz, M. Drozdowski, P. Formanowicz, W. Kubiak and G. Schmidt, Scheduling preemtable tasks on parallel processors with limited availability. Parallel Comput. 26 (2000) 1195-1211. | Zbl 0945.68015

[3] J. Błażewicz, K. Ecker, E. Pesch, G. Schmidt and J. Wȩglarz, Scheduling Computer and Manufacturing Processes, 2nd Edition. Springer-Verlag, Berlin (2001). | Zbl 0985.90033

[4] D. Dolev and M.K. Warmuth, Profile scheduling of opposing forests and level orders. SIAM J. Algebraic Discrete Meth. 6 (1985) 665-687. | MR 800997 | Zbl 0577.90038

[5] D. Dolev and M. Warmuth, Scheduling flat graphs. SIAM J. Comput. 14 (1985) 638-657. | MR 795936 | Zbl 0604.68038

[6] P. Formanowicz, Scheduling jobs in systems with limited availability of processors (in Polish), Ph.D. Thesis. Institute of Computing Science, Poznań University of Technology, Poznań (2000).

[7] P. Formanowicz, Selected deterministic scheduling problems with limited machine availability. Pro Dialog 13 (2001) 91-105.

[8] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979). | MR 519066 | Zbl 0411.68039

[9] M.R. Garey, D.S. Johnson, R.E. Tarjan and M. Yannakakis, Scheduling opposing forests. SIAM J. Alg. Disc. Meth. 4 (1983) 72-93. | MR 689869 | Zbl 0507.68021

[10] W. Kubiak, J. Błażewicz, P. Formanowicz, J. Breit and G. Schmidt, Two-machine flow shops with limited machine availability. Eur. J. Oper. Res. 136 (2002) 528-540. | Zbl 1007.90026

[11] C.-Y. Lee, Machine scheduling with an availability constraint. J. Global Optim. 9 (1996) 395-416. | MR 1421836 | Zbl 0870.90071

[12] C.-Y. Lee, Minimizing the makespan in the two-machine flow shop scheduling problem with an availability constraint. Oper. Res. Lett. 20 (1997) 129-139. | MR 1449340 | Zbl 0882.90069

[13] C.-Y. Lee, Two-machine flowshop scheduling with availability constraints. Eur. J. Oper. Res. 114 (1999) 420-429. | Zbl 0971.90031

[14] Z. Liu and E. Sanlaville, Preemptive scheduling with variable profile, precedence constraints and due dates. Discrete Appl. Math. 58 (1995) 253-280. | MR 1326050 | Zbl 0833.90071

[15] E. Sanlaville and G. Schmidt, Machine scheduling with availability constraints. Acta Informatica 35 (1998) 795-811. | MR 1645421 | Zbl 0917.68018

[16] G. Schmidt, Scheduling on semi-identical processors. Z. Oper. Res. A 28 (1984) 153-162. | MR 770929 | Zbl 0551.90044

[17] G. Schmidt, Scheduling independent tasks with deadlines on semi-identical processors. J. Oper. Res. Soc. 39 (1988) 271-277. | Zbl 0657.90051

[18] G. Schmidt, Scheduling with limited machine availability. Eur. J. Oper. Res. 121 (2000) 1-15. | MR 1780976 | Zbl 0959.90023