# Job shop, disjunctive formulation
#
# Schedules multi-operation jobs across machines where each job visits the
# machines in its own order. Two constraint families do the work: precedence
# within a job is a plain inequality, while non-interference on a machine
# needs the disjunctive pair, since either operation may go first.
#
# Technique: Precedence rows inside each job, plus a big-M either-or pair
# for every pair of operations sharing a machine.
#
# On this instance the optimum is 7 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Manne, A. S. (1960). On the job-shop scheduling problem.
# Operations Research 8(2), 219–223.
model m
set J = {1, 2}
set M = {1, 2}
set P = {1, 2}
const d = {{4, 1},
{2, 2}}, forall j in J, forall k in M
const H = 9
var 0 <= s <= 9, forall j in J, forall k in M
var 0 <= mk <= 9
bin y, forall q in P
min mk
# each job runs machine 1 before machine 2
constr s_{j,2} >= s_{j,1} + d_{j,1}, forall j in J
# makespan dominates every completion
constr mk >= s_{j,k} + d_{j,k}, forall j in J, forall k in M
# on each machine the two jobs cannot overlap; y picks which goes first
constr s_{2,q} >= s_{1,q} + d_{1,q} - H * [1 - y_{q}], forall q in P
constr s_{1,q} >= s_{2,q} + d_{2,q} - H * y_{q}, forall q in P
end
import elytica
Read this through MCP: read with path: "formulations/job-shop-disjunctive", or resource hlpl://formulations/job-shop-disjunctive.