direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content


Articles in Refereed Conference Proceedings

An experimental and analytical study of order constraints for single machine scheduling with quadratic cost
Citation key HoehnJacobs2012a
Author Höhn, Wiebke and Jacobs, Tobias
Title of Book Proc. of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX)
Pages 103-117
Year 2012
Publisher SIAM
Abstract We consider the problem of scheduling jobs on a single machine. Given a quadratic cost function, we aim to compute a schedule minimizing the weighted total cost, where the cost of each job is defined as the cost function value at the job's completion time. Throughout the past decades, great effort has been made to develop fast exact algorithms for the case of quadratic costs. The efficiency of these methods heavily depends on the utilization of structural properties of optimal schedules such as order constraints, i.e., sufficient conditions for pairs of jobs to appear in a certain order. A considerable number of different kinds of such constraints have been proposed. In this work we enhance the map of known order constraints by proving an extended version of a constraint that has been conjectured by Mondal and Sen more than a decade ago. Besides proving this conjecture, our main contribution is an extensive experimental study where the influence of different kinds order constraints on the performance of exact algorithms is systematically evaluated. In addition to a best-first graph search algorithm, we test a Quadratic Integer Programming formulation that admits to add order constraints as additional linear constraints. We also evaluate the optimality gap of well known Smith's rule for different monomial cost functions. Our experiments are based on sets of problem instances that have been generated using a new method which allows us to adjust a certain degree of difficulty of the instances.
Link to 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.