Scheduling jobs in open shops with limited machine availability
Jacek Błażewicz; Piotr Formanowicz
RAIRO - Operations Research (2010)
- Volume: 36, Issue: 2, page 149-156
- ISSN: 0399-0559
Access Full Article
top
Abstract
topHow to cite
topBłażewicz, Jacek, and Formanowicz, Piotr. "Scheduling jobs in open shops with limited machine availability." RAIRO - Operations Research 36.2 (2010): 149-156. <http://eudml.org/doc/105266>.
@article{Błażewicz2010,
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},
keywords = {Limited machine availability; computational complexity;
two-phase method; mathematical programming.; two-phase method; mathematical programming},
language = {eng},
month = {3},
number = {2},
pages = {149-156},
publisher = {EDP Sciences},
title = {Scheduling jobs in open shops with limited machine availability},
url = {http://eudml.org/doc/105266},
volume = {36},
year = {2010},
}
TY - JOUR
AU - Błażewicz, Jacek
AU - Formanowicz, Piotr
TI - Scheduling jobs in open shops with limited machine availability
JO - RAIRO - Operations Research
DA - 2010/3//
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.; two-phase method; mathematical programming
UR - http://eudml.org/doc/105266
ER -
References
top- J. Błazewicz, 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.
- J. Błazewicz, M. Drozdowski, P. Formanowicz, W. Kubiak and G. Schmidt, Scheduling preemtable tasks on parallel processors with limited availability. Parallel Comput.26 (2000) 1195-1211.
- J. Błazewicz, K. Ecker, E. Pesch, G. Schmidt and J. Weglarz, Scheduling Computer and Manufacturing Processes, 2nd Edition. Springer-Verlag, Berlin (2001).
- D. Dolev and M.K. Warmuth, Profile scheduling of opposing forests and level orders. SIAM J. Algebraic Discrete Meth.6 (1985) 665-687.
- D. Dolev and M. Warmuth, Scheduling flat graphs. SIAM J. Comput.14 (1985) 638-657.
- P. Formanowicz, Scheduling jobs in systems with limited availability of processors (in Polish), Ph.D. Thesis. Institute of Computing Science, Poznan University of Technology, Poznan (2000).
- P. Formanowicz, Selected deterministic scheduling problems with limited machine availability. Pro Dialog13 (2001) 91-105.
- M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979).
- M.R. Garey, D.S. Johnson, R.E. Tarjan and M. Yannakakis, Scheduling opposing forests. SIAM J. Alg. Disc. Meth.4 (1983) 72-93.
- W. Kubiak, J. Błazewicz, P. Formanowicz, J. Breit and G. Schmidt, Two-machine flow shops with limited machine availability. Eur. J. Oper. Res.136 (2002) 528-540.
- C.-Y. Lee, Machine scheduling with an availability constraint. J. Global Optim.9 (1996) 395-416.
- 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.
- C.-Y. Lee, Two-machine flowshop scheduling with availability constraints. Eur. J. Oper. Res.114 (1999) 420-429.
- Z. Liu and E. Sanlaville, Preemptive scheduling with variable profile, precedence constraints and due dates. Discrete Appl. Math.58 (1995) 253-280.
- E. Sanlaville and G. Schmidt, Machine scheduling with availability constraints. Acta Informatica35 (1998) 795-811.
- G. Schmidt, Scheduling on semi-identical processors. Z. Oper. Res. A28 (1984) 153-162.
- G. Schmidt, Scheduling independent tasks with deadlines on semi-identical processors. J. Oper. Res. Soc.39 (1988) 271-277.
- G. Schmidt, Scheduling with limited machine availability. Eur. J. Oper. Res.121 (2000) 1-15.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.