FORMULATING THE SINGLE-MACHINE SEQUENCING PROBLEM WITH RELEASE DATES AS A MIXED INTEGER-PROGRAM

For the problem of minimising the weighted sum of start (or completion) times for the n-jobs, 1-machine problem with release dates, we consider a hierarchy of relaxations obtained by combining enumeration of initial sequences with Smith's rule. It is then shown that each of these relaxations can be formulated as a linear programming problem (i.e., the minimisation of a linear function over a polyhedron) in an enlarged space of variables. By projecting these polyhedra we obtain new valid inequalities for the problem, and in particular complete descriptions for 1-regular problems partially studied by Balas (1985) and Posner (1986). A second hierarchy of relaxations is obtained by studying various relaxations and alternative formulations from the literature. © 1990.