direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content


Articles in Refereed Conference Proceedings

On the performance of Smith's rule in single-machine scheduling with nonlinear cost
Citation key HoehnJacobs2012b
Author Höhn, Wiebke and Jacobs, Tobias
Title of Book Proc. of the 10th Latin American Theoretical Informatics Symposium (LATIN)
Pages 482-493
Year 2012
DOI 10.1007/978-3-642-29344-3_41
Volume 7256
Publisher Springer
Series LNCS
Abstract 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 to publication Link to original publication Download Bibtex entry

Journal Articles

Höhn, W. and Jacobs, T.
On the performance of Smith's rule in single-machine scheduling with nonlinear cost.
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.
Journal of Scheduling, Vol. 15, pp. 295-309, 2012.  [pdf]

Gellert, T., Höhn, W. and Möhring, R. H.
Sequencing and scheduling for filling lines in dairy production.
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.
Management Science, Vol. 57, pp. 647–666, 2011.
Finalist for the EURO Excellence in Practice Award 2009.  [pdf]

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.

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.