An experimental and analytical study of order constraints for single machine scheduling with quadratic cost

Research Area: Algorithms for Complex Scheduling Problems Year: 2012
Type of Publication: In Proceedings
Authors: Wiebke Höhn; Tobias Jacobs
Book title: Proc. of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX)
Pages: 103-117
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.
[ Back ]