×

SPT is optimally competitive for uniprocessor flow. (English) Zbl 1178.68688

Summary: We show that the Shortest Processing Time (SPT) algorithm is \((\Delta +1)/2\)-competitive for nonpreemptive uniprocessor total flow time with release dates, where \(\Delta \) is the ratio between the longest and shortest job lengths. This is best possible for a deterministic algorithm and improves on the \((\Delta +1)\)-competitive ratio shown by Epstein and van Stee using different methods.

MSC:

68W27 Online algorithms; streaming algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Awerbuch, B.; Azar, Y.; Leonardi, S.; Regev, O., Minimizing flow time without migration, (Proc. 31st Symp. on Theory of Computation (1999)), 198-205 · Zbl 1345.68025
[2] Epstein, L.; van Stee, R., Lower bounds for on-line single-machine scheduling, (Proc. 26th Symp. Math. Found. Comput. Sci.. Proc. 26th Symp. Math. Found. Comput. Sci., Lecture Notes in Comput. Sci., vol. 2136 (2001), Springer-Verlag: Springer-Verlag Berlin), 338-350 · Zbl 0999.68502
[3] Epstein, L.; van Stee, R., Optimal on-line flow time with resource augmentation, (Proc. 13th Symp. Fund. Comp. Theory. Proc. 13th Symp. Fund. Comp. Theory, Lecture Notes in Comput. Sci., vol. 2138 (2001), Springer-Verlag: Springer-Verlag Berlin), 472-482 · Zbl 0999.68023
[4] Kellerer, H.; Tautenhahn, T.; Woeginger, G. J., Approximability and nonapproximability results for minimizing total flow time on a single machine, SIAM J. Comput., 28, 4, 1155-1166 (1999) · Zbl 0926.68014
[5] Leonardi, S.; Raz, D., Approximating total flow time on parallel machines, (Proc. 29th Symp. on Theory of Computation (1997)), 110-119 · Zbl 0962.68007
[6] Schrage, L., A proof of the optimality of the shortest processing remaining time discipline, Oper. Res., 16, 687-690 (1968) · Zbl 0237.60039
[7] Smith, D., A new proof of the optimality of the shortest remaining processing time discipline, Oper. Res., 26, 1, 197-199 (1976) · Zbl 0373.60124
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.