A mixed-integer model for solving ordering problems with side constraints

The authors present an exact approach for solving the Sequential Ordering Problem. In this problem, a set of jobs has to be processed on a single machine; a time window (deadline-release data) is associated with each job, and precedence relationships between jobs are given. Moreover, a setup time (possibly zero) before processing a job is assigned. The problem consists in finding an ordering of the jobs such that the completion time of the job sequenced last is minimized. Starting from a 0-1 formulation of the problem, the authors translate the model into a linear Mixed Integer Program (MIP) problem by adding some variables representing the idle time of the machine, in such a way that both the subtour elimination constraints and the due forcing constraints are implicitly satisfied. Some computational experience is reported along with the analysis of a simple case study. The main goal of this work is to assess the suitability of the mathematical models presented with respect to available MIP software like OSL.