direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Publikationen

Publikationen in Konferenzbänden

On the performance of Smith's rule in single-machine scheduling with nonlinear cost
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.
Link zur Publikation [1] Link zur Originalpublikation [2] Download Bibtex Eintrag [3]

Zurück [4]

Publikationen in Journalen

Höhn, W. and Jacobs, T.
On the performance of Smith's rule in single-machine scheduling with nonlinear cost [5].
ACM Transactions on Algorithms, Vol. 11, pp. Article 25, 2015.

Höhn, W., Jacobs, T. and Megow, N.
On Eulerian extensions and their application to no-wait flowshop scheduling [6].
Journal of Scheduling, Vol. 15, pp. 295-309, 2012.  [pdf] [7]

Gellert, T., Höhn, W. and Möhring, R. H.
Sequencing and scheduling for filling lines in dairy production [8].
Optimization Letters, Vol. 5, pp. 491–504, 2011.
Special issue of SEA 2011.

Höhn, W., König, F. G., Lübbecke, M. E. and Möhring, R. H.
Integrated Sequencing and Scheduling in Coil Coating [9].
Management Science, Vol. 57, pp. 647–666, 2011.
Finalist for the EURO Excellence in Practice Award 2009.  [pdf] [10]

Doktorarbeit

Höhn, W.
Complex Single Machine Scheduling: Theoretical and Practical Aspects of Sequencing [11].
PhD thesis, TU Berlin, 2013.  [pdf] [12]

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.

------ Links: ------

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

Hilfsfunktionen

Schriftgröße:
kleiner
Standardgröße
größer
Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.
Copyright TU Berlin 2008