Parametric precedence relations in single machine scheduling

The paper provides a theoretical background to solve a variety of single machine scheduling problems with quadratic separable functions of completion times including waiting time and due date models. The approach is based on a parametric ordering as well as an adjacent precedence matrix concept. Rules are presented to decompose the problem into separate subproblems. Those rules are incorporated in a branch and bound procedure that also utilizes other properties of the precedence matrix. Necessary optimality conditions are given for two common due date models where lower bounds are not yet available.