Scheduling jobs in open shops with limited machine availability

Jacek Błażewicz; Piotr Formanowicz

RAIRO - Operations Research - Recherche Opérationnelle (2002)

  • Volume: 36, Issue: 2, page 149-156
  • ISSN: 0399-0559

Abstract

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

How to cite

top

Błażewicz, Jacek, and Formanowicz, Piotr. "Scheduling jobs in open shops with limited machine availability." RAIRO - Operations Research - Recherche Opérationnelle 36.2 (2002): 149-156. <http://eudml.org/doc/245719>.

@article{Błażewicz2002,
abstract = {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.},
author = {Błażewicz, Jacek, Formanowicz, Piotr},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {limited machine availability; computational complexity; two-phase method; mathematical programming},
language = {eng},
number = {2},
pages = {149-156},
publisher = {EDP-Sciences},
title = {Scheduling jobs in open shops with limited machine availability},
url = {http://eudml.org/doc/245719},
volume = {36},
year = {2002},
}

TY - JOUR
AU - Błażewicz, Jacek
AU - Formanowicz, Piotr
TI - Scheduling jobs in open shops with limited machine availability
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2002
PB - EDP-Sciences
VL - 36
IS - 2
SP - 149
EP - 156
AB - 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.
LA - eng
KW - limited machine availability; computational complexity; two-phase method; mathematical programming
UR - http://eudml.org/doc/245719
ER -

References

top
  1. [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. Zbl1007.90026
  2. [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. Zbl0945.68015
  3. [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). Zbl0985.90033
  4. [4] D. Dolev and M.K. Warmuth, Profile scheduling of opposing forests and level orders. SIAM J. Algebraic Discrete Meth. 6 (1985) 665-687. Zbl0577.90038MR800997
  5. [5] D. Dolev and M. Warmuth, Scheduling flat graphs. SIAM J. Comput. 14 (1985) 638-657. Zbl0604.68038MR795936
  6. [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. [7] P. Formanowicz, Selected deterministic scheduling problems with limited machine availability. Pro Dialog 13 (2001) 91-105. 
  8. [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). Zbl0411.68039MR519066
  9. [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. Zbl0507.68021MR689869
  10. [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. Zbl1007.90026
  11. [11] C.-Y. Lee, Machine scheduling with an availability constraint. J. Global Optim. 9 (1996) 395-416. Zbl0870.90071MR1421836
  12. [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. Zbl0882.90069MR1449340
  13. [13] C.-Y. Lee, Two-machine flowshop scheduling with availability constraints. Eur. J. Oper. Res. 114 (1999) 420-429. Zbl0971.90031
  14. [14] Z. Liu and E. Sanlaville, Preemptive scheduling with variable profile, precedence constraints and due dates. Discrete Appl. Math. 58 (1995) 253-280. Zbl0833.90071MR1326050
  15. [15] E. Sanlaville and G. Schmidt, Machine scheduling with availability constraints. Acta Informatica 35 (1998) 795-811. Zbl0917.68018MR1645421
  16. [16] G. Schmidt, Scheduling on semi-identical processors. Z. Oper. Res. A 28 (1984) 153-162. Zbl0551.90044MR770929
  17. [17] G. Schmidt, Scheduling independent tasks with deadlines on semi-identical processors. J. Oper. Res. Soc. 39 (1988) 271-277. Zbl0657.90051
  18. [18] G. Schmidt, Scheduling with limited machine availability. Eur. J. Oper. Res. 121 (2000) 1-15. Zbl0959.90023MR1780976

NotesEmbed ?

top

You must be logged in to post comments.