S3 sets. An extension of the Beale-Tomlin special ordered sets

In this work an extension of the Beale-Tomlin special ordered sets is introduced that has proved to be efficient for solving certain types of open shop scheduling problems. Besides their usual characteristics, exclusivity constraints in the jobs are allowed, more general than tree-like precedence structures are considered, and semi-active schedules that cannot be labeled as non-optimal solutions may occur. The problem is formulated as a large-scale 0–1 model. Computational experience on some real-life problems is reported.