A compact optimization approach for jobshop problems

In this paper we propose a time-indexed IP formulation for job-shop scheduling problems. We first introduce a model with variables associated to job scheduling patterns and constraints associated to machine capacities and to job assignments. The exponential number of variables calls for a column generation scheme which is carried out by a dynamic programming procedure. However, the column generation process is time-consuming. Therefore we derive an equivalent compact formulation of the model, whose dual is a flow problem with side constraints. This problem can be solved faster and fits easily into a branch-and-bound scheme