×

Single machine flow-time scheduling with scheduled maintenance. (English) Zbl 0738.68043

We investigate a single machine scheduling problem of minimizing the sum of job flow times subject to scheduled maintenance. We first provide NP- completeness proof for the problem. This proof is much shorter than the one given in the literature. The Shortest Processing Time (SPT) sequence is then shown to have a worst case error bound of 2/7. Furthermore, an example is provided to show that the bound is tight.

MSC:

68Q25 Analysis of algorithms and problem complexity
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B35 Deterministic scheduling theory in operations research
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Adiri I, Bruno J, Frostig E, Rinnooy Kan AHG: Single machine flow-time scheduling with a single breakdown. Acta Inf.26, 679-696 (1989) · Zbl 0657.68033
[2] Conway RW, Maxwell WL, Miller LW: Theory of scheduling. Reading, MA: Addison-Wesley 1967
[3] Garey MR, Tarjan RE, Wilfong GT: One-processor scheduling with symmetric earliness and tardiness penalties. Math. Oper. Res.13, 330-348 (1988) · Zbl 0671.90033
[4] Smith WE: Various optimizers for single stage production. Naval Res. Log. Qu.3, 59-66 (1956)
[5] Garey MR, Tarjan RE, Wilfong GT: One-processor scheduling with symmetric earliness and tardiness penalties. Math. Oper. Res.13, 330-348 (1988) · Zbl 0671.90033
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.