×

Scheduling with limited machine availability. (English) Zbl 0959.90023

Summary: This paper reviews results related to deterministic scheduling problems where machines are not continuously available for processing. There might be incomplete information about the points of time machines change availability. The complexity of single and multi machine problems is analyzed considering criteria on completion times and due dates. The review mainly covers intractability results, polynomial optimization and approximation algorithms. In some places two results from enumerative algorithms and heuristics are surveyed.

MSC:

90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adiri, I.; Bruno, J.; Frostig, E.; Rinnooy Kan, A. H.G., Single machine flow-time scheduling with a single breakdown, Acta Informatica, 26, 679-696 (1989) · Zbl 0657.68033
[2] S. Albers, G. Schmidt, Scheduling with unexpected machine breakdowns, Technical Report MPI-I-98-1-021, Max Planck Institut für Informatik, Saarbrücken, 1998; S. Albers, G. Schmidt, Scheduling with unexpected machine breakdowns, Technical Report MPI-I-98-1-021, Max Planck Institut für Informatik, Saarbrücken, 1998 · Zbl 0949.68013
[3] J. Blazewicz, J. Breit, P. Formanowicz, W. Kubiak, G. Schmidt, Heuristics for two machine flow shops with limited machine availability, Discussion Paper B-9802, Fachbereich Wirtschaftswissenschaft, University of Saarland, 1998; J. Blazewicz, J. Breit, P. Formanowicz, W. Kubiak, G. Schmidt, Heuristics for two machine flow shops with limited machine availability, Discussion Paper B-9802, Fachbereich Wirtschaftswissenschaft, University of Saarland, 1998 · Zbl 1007.90026
[4] J. Blazewicz, M. Drozdowski, P. Formanowicz, W. Kubiak, G. Schmidt, Scheduling preemtable tasks on parallel processors with limited availability, unpublished; J. Blazewicz, M. Drozdowski, P. Formanowicz, W. Kubiak, G. Schmidt, Scheduling preemtable tasks on parallel processors with limited availability, unpublished
[5] J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt, J. Weglarz, Scheduling Computer and Manufacturing Processes, Springer, Berlin, 1996; J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt, J. Weglarz, Scheduling Computer and Manufacturing Processes, Springer, Berlin, 1996 · Zbl 0911.90201
[6] J. Blazewicz, P. Formanowicz, W. Kubiak, G. Schmidt, A note on a parallel branch and bound algorithm for the flow shop problem with limited machine availability, Working Paper, Poznan Supercomputing and Networking Center, Poznan, 1997; J. Blazewicz, P. Formanowicz, W. Kubiak, G. Schmidt, A note on a parallel branch and bound algorithm for the flow shop problem with limited machine availability, Working Paper, Poznan Supercomputing and Networking Center, Poznan, 1997 · Zbl 0957.68011
[7] Chen, B.; Van Vliet, A.; Woeginger, G. J., A lower bound for randomized on-line scheduling algorithms, Information Processing Letters, 51, 219-222 (1994) · Zbl 0821.68011
[8] Dolev, D.; Warmuth, M. K., Scheduling flat graphs, SIAM Journal on Computing, 14, 638-657 (1985) · Zbl 0604.68038
[9] Dolev, D.; Warmuth, M. K., Profile scheduling of opposing forests and level orders, SIAM Journal on Algebraic and Discrete Methods, 6, 665-687 (1985) · Zbl 0577.90038
[10] M.R. Garey, D.S. Johnson, Computers and Intractability, Freeman, San Francisco, 1979; M.R. Garey, D.S. Johnson, Computers and Intractability, Freeman, San Francisco, 1979
[11] Graham, R. L., Bounds on multiprocessing timing anomalies, SIAM Journal on Applied Mathematics, 17, 263-269 (1969) · Zbl 0188.23101
[12] Horn, W. A., Some simple scheduling algorithms, Naval Research Logistics Quarterly, 21, 177-185 (1974) · Zbl 0276.90024
[13] Johnson, S. M., Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, 61-68 (1954) · Zbl 1349.90359
[14] B. Kalyanasundaram, K.P. Pruhs, Fault-tolerant scheduling, in: Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, 1994, pp. 115-124; B. Kalyanasundaram, K.P. Pruhs, Fault-tolerant scheduling, in: Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, 1994, pp. 115-124 · Zbl 1344.68038
[15] B. Kalyanasundaram, K.P. Pruhs, Fault-tolerant real-time scheduling, in: Proceedings of the Fifth Annual European Symposium on Algorithms (ESA), Springer Lecture Notes in Computer Science, 1997; B. Kalyanasundaram, K.P. Pruhs, Fault-tolerant real-time scheduling, in: Proceedings of the Fifth Annual European Symposium on Algorithms (ESA), Springer Lecture Notes in Computer Science, 1997 · Zbl 0959.68010
[16] R.M. Karp, Reducibility among combinatorial problems, in: R.E. Miller, J.W. Thatcher (Eds.), Complexity of Computer Communications, Plenum Press, New York, 1972, pp. 85-103; R.M. Karp, Reducibility among combinatorial problems, in: R.E. Miller, J.W. Thatcher (Eds.), Complexity of Computer Communications, Plenum Press, New York, 1972, pp. 85-103
[17] M. Kaspi, B. Montreuil, On the scheduling of identical parallel processes with arbitrary initial processor available time, Research Report 88-12, School of Industrial Engineering, Purdue University, West Lafayette, IN, 1988; M. Kaspi, B. Montreuil, On the scheduling of identical parallel processes with arbitrary initial processor available time, Research Report 88-12, School of Industrial Engineering, Purdue University, West Lafayette, IN, 1988
[18] H. Kellerer, Algorithms for multiprocessor scheduling with machine release time, IIE Transactions (to appear); H. Kellerer, Algorithms for multiprocessor scheduling with machine release time, IIE Transactions (to appear) · Zbl 1335.90037
[19] W. Kubiak, J. Blazewicz, P. Formanowicz, G. Schmidt, A branch and bound algorithm for two machine flow shops with limited machine availability, Research Report RA-001/97, Poznan University of Technology, Institute of Computing Science, Poznan, 1997; W. Kubiak, J. Blazewicz, P. Formanowicz, G. Schmidt, A branch and bound algorithm for two machine flow shops with limited machine availability, Research Report RA-001/97, Poznan University of Technology, Institute of Computing Science, Poznan, 1997 · Zbl 0957.68011
[20] J. Labetoulle, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, Preemptive scheduling of uniform machines subject to due dates, Technical Paper BW 99/79, CWI, Amsterdam, 1979; J. Labetoulle, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, Preemptive scheduling of uniform machines subject to due dates, Technical Paper BW 99/79, CWI, Amsterdam, 1979 · Zbl 0554.90059
[21] E.L. Lawler, Preemptive scheduling of precedence constrained jobs on parallel machines, in: Dempster et al. (Eds.), Deterministic and Stochastic Scheduling, Reidel, Boston, 1982, pp. 101-123; E.L. Lawler, Preemptive scheduling of precedence constrained jobs on parallel machines, in: Dempster et al. (Eds.), Deterministic and Stochastic Scheduling, Reidel, Boston, 1982, pp. 101-123 · Zbl 0495.68031
[22] Lawler, E. L.; Martel, C. U., Preemptive scheduling of two uniform machines to minimize the number of late jobs, Operations Research, 37, 314-318 (1989) · Zbl 0672.90071
[23] Lee, C.-Y., Parallel machine scheduling with non-simultaneous machine available time, Discrete Applied Mathematics, 30, 53-61 (1991) · Zbl 0722.90032
[24] Lee, C.-Y., Machine scheduling with an availability constraint, Journal of Global Optimization, Special Issue on Optimization of Scheduling Applications, 9, 363-384 (1996)
[25] Lee, C.-Y., Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint, Operations Research Letters, 20, 129-139 (1997) · Zbl 0882.90069
[26] Lee, C.-Y.; Liman, S. D., Single machine flow-time scheduling with scheduled maintenance, Acta Informatica, 29, 375-382 (1992) · Zbl 0738.68043
[27] Lee, C.-Y.; Liman, S. D., Capacitated two-parallel machine scheduling to minimize sum of job completion times, Discrete Applied Mathematics, 41, 211-222 (1993) · Zbl 0778.90028
[28] Lee, C. Y.; Lei, L.; Pinedo, M., Current trends in deterministic scheduling, Annals of Operations Research, 70, 1-42 (1997) · Zbl 0890.90102
[29] Lenstra, J. K.; Rinnooy Kan, A. H.G.; Brucker, P., Complexity of processor scheduling problems, Annals Discrete Mathematics, 1, 343-362 (1977) · Zbl 0353.68067
[30] S. Liman, Scheduling with capacities and due-dates, Ph.D. Thesis, University of Florida, Gainesville, FL, 1991; S. Liman, Scheduling with capacities and due-dates, Ph.D. Thesis, University of Florida, Gainesville, FL, 1991
[31] Lin, G.; He, Y.; Yao, Y.; Lu, H., Exact bounds of the modified LPT algorithm applying to parallel machines scheduling with nonsimultaneous machine available times, Applied Mathematics Journal of the Chinese University, B 12, 1, 109-116 (1997) · Zbl 0884.90104
[32] Liu, Z.; Sanlaville, E., Preemptive scheduling with variable profile, precedence constraints and due dates, Discrete Applied Mathematics, 58, 253-280 (1995) · Zbl 0833.90071
[33] Z. Liu, E. Sanlaville, Profile scheduling of list algorithms, in: P. Chretienne et al. (Eds.), Scheduling Theory and its Applications, Wiley, New York, 1995, pp. 91-110; Z. Liu, E. Sanlaville, Profile scheduling of list algorithms, in: P. Chretienne et al. (Eds.), Scheduling Theory and its Applications, Wiley, New York, 1995, pp. 91-110
[34] Liu, Z.; Sanlaville, E., Stochastic scheduling with variable profile and precedence constraints, SIAM Journal on Computing, 26, 173-187 (1997) · Zbl 0872.90049
[35] Muntz, R.; Coffman, E. G., Preemptive scheduling of real-time tasks on multiprocessor systems, Journal of the Association for Computing Machinery, 17, 324-338 (1970) · Zbl 0216.49702
[36] McNaughton, R., Scheduling with deadlines and loss functions, Management Science, 6, 1-12 (1959) · Zbl 1047.90504
[37] Moore, J. M., An \(n\) job one machine sequencing algorithm for minimizing the number of late jobs, Management Science, 15, 102-109 (1968) · Zbl 0164.20002
[38] T.E. Morton, D.W. Pentico, Heuristic Scheduling Systems, Wiley, New York, 1993; T.E. Morton, D.W. Pentico, Heuristic Scheduling Systems, Wiley, New York, 1993
[39] Mosheiov, G., Minimizing the sum of job completion times on capacitated parallel machines, Mathematical Computing and Modelling, 20, 91-99 (1994) · Zbl 0810.90072
[40] E. Sanlaville, Nearly on line scheduling of preemptive independent tasks, Discrete Applied Mathematics 57, 229-241; E. Sanlaville, Nearly on line scheduling of preemptive independent tasks, Discrete Applied Mathematics 57, 229-241 · Zbl 0830.68011
[41] Schmidt, G., Scheduling on semi-identical processors, Zeitschrift fur Operations Research, A 28, 153-162 (1984) · Zbl 0551.90044
[42] Schmidt, G., Scheduling independent tasks with deadlines on semi-identical processors, Journal of the Operational Research Society, 39, 271-277 (1988) · Zbl 0657.90051
[43] Sleator, D. D.; Tarjan, R. E., Amortized efficiency of list update and paging rules, Communications of the Association for Computing Machinery, 28, 202-208 (1985)
[44] Smith, W. E., Various optimizers for single-stage production, Naval Research Logistics Quarterly, 3, 59-66 (1956)
[45] Ullman, J. D., NP-complete scheduling problems, Journal of Computer and System Sciences, 10, 384-393 (1975) · Zbl 0313.68054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.