Inhalt des Dokuments
zur Navigation
Publikationen
Siehe auch: google scholar; DBLP; zbMath; MathSciNet
| Zitatschlüssel | JaegerSkutella2018 |
|---|---|
| Autor | Jäger, Sven and Skutella, Martin |
| Buchtitel | 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) |
| Seiten | 43:1–43:14 |
| Jahr | 2018 |
| ISBN | 978-3-95977-062-0 |
| ISSN | 1868-8969 |
| DOI | 10.4230/LIPIcs.STACS.2018.43 |
| Ort | Caen |
| Adresse | Dagstuhl, Germany |
| Jahrgang | 96 |
| Herausgeber | Niedermeier, Rolf and Vallée, Brigitte |
| Verlag | Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik |
| Serie | Leibniz International Proceedings in Informatics (LIPIcs) |
| Zusammenfassung | Minimizing the sum of weighted completion times on m identical parallel machines is one of the most important and classical scheduling problems. For the stochastic variant where processing times of jobs are random variables, Möhring, Schulz, and Uetz (1999) presented the first and still best known approximation result, achieving, for arbitrarily many machines, performance ratio 1+1/2(1+Δ), where Δ is an upper bound on the squared coefficient of variation of the processing times. We prove performance ratio 1+1/2(√2-1)(1+Δ) for the same underlying algorithm–-the Weighted Shortest Expected Processing Time (WSEPT) rule. For the special case of deterministic scheduling (i.e., Δ=0), our bound matches the tight performance ratio 1/2(1+√2) of this algorithm (WSPT rule), derived by Kawaguchi and Kyan in a 1986 landmark paper. We present several further improvements for WSEPT's performance ratio, one of them relying on a carefully refined analysis of WSPT yielding, for every fixed number of machines m, WSPT's exact performance ratio of order 1/2(1+√2)-O(1/m²). |
Copyright notice
The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.