On-line scheduling revisited. (English) Zbl 0966.90032
Summary: We present a new on-line algorithm, MR, for non-preemptive scheduling of jobs with known processing times on \(m\) identical machines which beats the best previous algorithm for \(m\geq 64\). For \(m\to\infty\) its competitive ratio approaches \(1+\sqrt {(1+\ln 2)/2} <1.9201\).
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Computers and Intractability?A Guide to the Theory of NP-Completeness. W.H. Freeman and Company: New York, 1979. · Zbl 0411.68039 |
| [2] | Online Computation and Competitive Analysis. Cambridge University Press: Cambridge, England, 1998. · Zbl 0931.68015 |
| [3] | (eds). Online Algorithms?The State of the Art. Springer Lecture Notes in Computer Science, vol. 1442. Springer: Heidelberg, 1998. · Zbl 1177.68009 |
| [9] | Better bounds for online scheduling. In Proceedings of the 29th ACM Symposium on the Theory of Computation (STOC’97), 1997; 130-139. SIAM Journal on Computing, to appear. · Zbl 0968.68008 |
| [12] | Generating adversaries for request-answer games. In Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms (SODA’00), 2000; 564-565. · Zbl 0962.91001 |
| [16] | Randomized algorithms for that ancient scheduling problem. In Proceedings of the 5th Workshop on Algorithms and Data Structures (WADS’97). Springer Lecture Notes in Computer Science, vol. 1272. 1997; 210-223. |
| [18] | (ed.). Approximation Algorithms for NP-Hard Problems. PWS Publishing Company: Boston, MA, 1996. · Zbl 1368.68010 |
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.
