×

Single machine flow-time scheduling with a single breakdown. (English) Zbl 0657.68033

We consider the problem of scheduling tasks on a single machine to minimize the flowtime. The machine is subject to breakdowns during the processing of the tasks. The breakdowns occur at random times and the machine is unavailable until it is repaired. The times for repair are random and independent of each other and of the breakdown process. A task that is preempted due to a breakdown must be restarted and otherwise preemptions are not allowed. We show in the case of a single breakdown that if the distribution function of the time to breakdown is concave then shortest processing time (SPT) first scheduling stochastically minimizes the flowtime.
For the case of multiple breakdowns we show that SPT minimizes the expected flowtime when the times to breakdown are exponentially distributed. If the time for a single breakdown is known before scheduling begins, and the processing times of the tasks are also known, then we show that the problem of deciding whether there is a schedule with flowtime less than or equal to a given value is NP-complete. Finally, we bound the performance of SPT scheduling in the deterministic case when there is a single breakdown.
Reviewer: I.Adiri

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68Q25 Analysis of algorithms and problem complexity
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. TRCS892, January 1989, Department of Computer Science, University of California, Santa Barbara, CA, 93106, USA · Zbl 0657.68033
[2] Coffman, E.G.: Computer and Job-Shop Scheduling Theory. New York: John Wiley 1976 · Zbl 0359.90031
[3] Conway, R.W., Maxwell, W.L., Miller, L.W.: Theory of Scheduling. Reading, MA: Addison-Wesley 1967
[4] Dempster, M.A.H., Lenstra, J.K., Rinnooy Kan, A.H.G.: Deterministic and Stochastic Scheduling. In: Proceedings of the NATO Advanced Study and Research Institute on Theoretical Approaches to Scheduling Problems. Dordrecht: Reidel 1982
[5] Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. San Francisco: Freeman 1979 · Zbl 0411.68039
[6] Smith, W.E.: Various Optimizers for Single-Stage Production. Nav. Res. Logist. Q. 3, 59-66 (1956) · doi:10.1002/nav.3800030106
[7] Strauch, R.: Negative Dynamic Programming. Ann. Math. Stat., 37, 871-890 (1966) · Zbl 0144.43201 · doi:10.1214/aoms/1177699369
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.