Loading…
Single Machine Scheduling with Weighted Nonlinear Cost
Höhn, Wiebke; Jacobs, Tobias
Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
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.
