Inhalt des Dokuments
zur Navigation
Publikationen in Konferenzbänden
| Zitatschlüssel | HoehnJacobs2012b |
|---|---|
| Autor | Höhn, Wiebke and Jacobs, Tobias |
| Buchtitel | Proc. of the 10th Latin American Theoretical Informatics Symposium (LATIN) |
| Seiten | 482-493 |
| Jahr | 2012 |
| DOI | 10.1007/978-3-642-29344-3_41 |
| Jahrgang | 7256 |
| Verlag | Springer |
| Serie | LNCS |
| Zusammenfassung | We consider the problem of scheduling jobs on a single machine. Given some continuous cost function, we aim to compute a schedule minimizing the weighted total cost, where the cost of each individual job is determined by the cost function value at the job's completion time. This problem is closely related to scheduling a single machine with nonuniform processing speed. We show that for piecewise linear cost functions it is strongly NP-hard. The main contribution of this article is a tight analysis of the approximation factor of Smith's rule under any particular convex or concave cost function. More specifically, for these wide classes of cost functions we reduce the task of determining a worst case problem instance to a continuous optimization problem, which can be solved by standard algebraic or numerical methods. For polynomial cost functions with positive coefficients it turns out that the tight approximation ratio can be calculated as the root of a univariate polynomial. To overcome unrealistic worst case instances, we also give tight bounds that are parameterized by the minimum, maximum, and total processing time. |
Hinweis zum Copyright
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.