Alternative graph formulation for solving complex factory-scheduling problems

The adaptation of the academic job shop scheduling model to industrial practice is well known to be rich of difficulties owing to the gap between scheduling theory and practice. On the other hand, several authors observed that the disjunctive graph formulation of Roy and Sussman was more robust than the job shop model itself. In fact, the disjunctive graph can be easily adapted to deal with many practical issues. This paper moves a step closer in the direction of generalizing the existing mathematical models in order to capture relevant aspects of complex factory scheduling problems. It considers an extension to the disjunctive graph, called an alternative graph, and allows it to be modelled in a precise way to solve effectively a number of complex practical scheduling problems for which there were no successful methodologies. Several examples are presented and a complex industrial application arising in the production of steel is provided. Finally, the performance of a new fast heuristic both on real data and several instances from the literature is discussed in relation to the job shop scheduling problem.