direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments


Single Machine Scheduling with Weighted Nonlinear Cost
Zitatschlüssel Report-008-2011
Autor Höhn, Wiebke and Jacobs, Tobias
Jahr 2011
Nummer 008
Monat mar
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We consider the problem of scheduling jobs on a single machine. Given a nonlinear 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 optimal branch-and-bound algorithms for the case of quadratic costs. The practical 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. The first part of this paper substantially enhances and generalizes the known order constraints. We prove a stronger version of the global order conjecture by Mondal and Sen that has remained open since 2000, and we generalize the two main types of local order constraints to a large class of polynomial cost functions. The new constraints directly give rise to branch-and-bound algorithms with improved efficiency. We take a different route in the second part of this paper and demonstrate the usefulness of order constraints as analytical tools. The WSPT rule, which is well-known to be optimal in the linear cost case, is proven to approximate optimal schedules up to a constant factor that equals the degree of the cost function when the latter is a polynomial with nonnegative coefficients. Furthermore, we give a slightly modified algorithm improving that factor; from 2 to 1.75 in the quadratic case. The previously best known approximation ratio achieved for all these problems is 16
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag