×

The complexity of machine scheduling for stability with a single disrupted job. (English) Zbl 1099.90020

Summary: A stable schedule is a robust schedule that will change little when uncertain events occur. The purpose of this paper is to investigate the complexity status of a number of machine scheduling problems with stability objective, when the duration of a single job is anticipated to be disrupted.

MSC:

90B35 Deterministic scheduling theory in operations research
90C31 Sensitivity, stability, parametric optimization
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 Inform, 36, 679-696 (1989) · Zbl 0657.68033
[2] Akturk, M. S.; Gorgulu, E., Match-up scheduling under a machine breakdown, European J. Oper. Res, 112, 81-97 (1999) · Zbl 0937.90029
[3] H. Aytug, M.A. Lawley, K. McKay, S. Mohan, R. Uzsoy, Executing production schedules in the face of uncertainties: a review and some future directions, European J. Oper. Res. (2004), to appear.; H. Aytug, M.A. Lawley, K. McKay, S. Mohan, R. Uzsoy, Executing production schedules in the face of uncertainties: a review and some future directions, European J. Oper. Res. (2004), to appear. · Zbl 1115.90025
[4] Bean, J. C.; Birge, J. R.; Mittenthal, J.; Noon, C. E., Match-up scheduling with multiple resources, release dates and disruptions, Oper. Res, 39, 470-483 (1991) · Zbl 0742.90041
[5] Bruno, J.; Coffmann, E. G.; Sethi, R., Scheduling independent tasks to reduce mean finishing time, Comm. ACM, 17, 382-387 (1974) · Zbl 0283.68039
[6] Daniels, R. L.; Carrillo, J. E., \(β\)-robust scheduling for single-machine systems with uncertain processing times, IIE Trans, 29, 977-985 (1997)
[7] Daniels, R. L.; Kouvelis, P., Robust scheduling to hedge against processing time uncertainty in single-stage production, Management Sci, 41, 363-376 (1995) · Zbl 0832.90050
[8] Du, J.; Leung, J. Y.-T.; Young, G. H., Scheduling chain-structured tasks to minimize makespan and mean flow time, Inform. Comput, 92, 219-236 (1991) · Zbl 0754.90029
[9] Garey, M. R.; Johnson, D. S., Computers and Intractability. A Guide to the Theory of NP-completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[10] N.G. Hall, C.N. Potts, Rescheduling for new orders, Oper. Res. (2004), to appear.; N.G. Hall, C.N. Potts, Rescheduling for new orders, Oper. Res. (2004), to appear. · Zbl 1165.90456
[11] Herroelen, W.; Leus, R., The construction of stable project baseline schedules, European J. Oper. Res, 156, 550-565 (2004) · Zbl 1056.90066
[12] Kouvelis, P.; Yu, G., Robust Discrete Optimization and Its Applications (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 0873.90071
[13] Lawler, E. L., Optimal sequencing of a single machine subject to precedence constraints, Manage. Sci, 19, 544-546 (1973) · Zbl 0254.90039
[14] Lawler, E. L., Sequencing jobs to minimize total weighted completion time subject to precedence constraints, Ann. Discrete Math, 2, 75-90 (1978) · Zbl 0374.68033
[15] Lenstra, J. K.; Rinnooy Kan, A. H.G., Complexity of scheduling under precedence constraints, Oper. Res, 26, 22-35 (1978) · Zbl 0371.90060
[16] Lenstra, J. K.; Rinnooy Kan, A. H.G.; Brucker, P., Complexity of machine scheduling problems, Ann. Discrete Math, 1, 343-362 (1977) · Zbl 0301.90025
[17] Leon, V. J.; Wu, S. D.; Storer, R. H., Robustness measures and robust scheduling for job shops, IIE Trans, 26, 32-43 (1994)
[18] Mehta, S. V.; Uzsoy, R. M., Predictable scheduling of a job shop subject to breakdowns, IEEE Trans. Robot. Automat, 14, 365-378 (1998)
[19] O’Donovan, R.; Uzsoy, R.; McKay, K. N., Predictable scheduling of a single machine with breakdowns and sensitive jobs, Internat J. Product. Res, 37, 4217-4233 (1999) · Zbl 0948.90554
[20] Pinedo, M., Scheduling. Theory, Algorithms and Systems (1995), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 1145.90393
[21] Raheja, A. S.; Subramaniam, V., Reactive recovery of job shop schedules—a review, Internat. J. Adv. Manuf. Technol, 19, 756-763 (2002)
[22] Rangsaritratsamee, R.; Ferrel, W. G.; Kurz, M. B., Dynamic rescheduling that simultaneously considers efficiency and stability, Comput. Ind. Eng, 46, 1-15 (2004)
[23] F. Stork, Stochastic resource-constrained project scheduling, Ph.D. Thesis, Technische Universität Berlin, 2001.; F. Stork, Stochastic resource-constrained project scheduling, Ph.D. Thesis, Technische Universität Berlin, 2001.
[24] Wu, S. D.; Storer, H. S.; Chang, P.-C., One-machine rescheduling heuristics with efficiency and stability as criteria, Comput. Oper. Res, 20, 1-14 (1993) · Zbl 0759.90049
[25] Yáñez, J.; Ramı́rez, J., The robust coloring problem, European J. Oper. Res, 148, 546-558 (2003) · Zbl 1035.90077
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.