Single machine flow-time scheduling with a single breakdown.

*(English)*Zbl 0657.68033We 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.

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 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.