# Single-machine sequencing, disjunctive (big-M) formulation
#
# Sequences jobs on one machine to minimise the makespan-equivalent
# completion of the last job. Time stays continuous and only the pairwise
# ordering is discrete, which keeps the model small — but the big-M rows
# give a weak relaxation, since a fractional y_ij releases both orderings at
# once.
#
# Technique: Continuous start times with a binary per pair deciding the
# order: s_j >= s_i + p_i - M(1 - y_ij) and the mirrored
# inequality.
#
# On this instance the optimum is 9 (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, 3, 4}
set P = {1, 2, 3, 4, 5, 6}
const p = {1, 1, 1, 6}, forall j in J
const rel = {1, 0, 2, 2}, forall j in J
const M = 12
var 0 <= s <= 11, forall j in J
var 0 <= mk <= 11
bin y, forall q in P
min mk
# no job starts before it is released
constr s_{j} >= rel_{j}, forall j in J
# makespan dominates every completion
constr mk >= s_{j} + p_{j}, forall j in J
# for each pair exactly one order holds; the other row is relaxed by M
constr s_{second(q)} >= s_{first(q)} + p_{first(q)} - M * [1 - y_{q}], forall q in P
constr s_{first(q)} >= s_{second(q)} + p_{second(q)} - M * y_{q}, forall q in P
end
import elytica
def first(q):
return {1: 1, 2: 1, 3: 1, 4: 2, 5: 2, 6: 3}[q]
def second(q):
return {1: 2, 2: 3, 3: 4, 4: 3, 5: 4, 6: 4}[q]
Read this through MCP: read with path: "formulations/single-machine-disjunctive", or resource hlpl://formulations/single-machine-disjunctive.