# Time-indexed scheduling
#
# Schedules jobs by deciding which period each one starts in. Far more
# variables than the disjunctive form — one per job-period pair — but the
# relaxation is much tighter and resource limits become a single sum per
# period instead of a big-M pair per job pair.
#
# Technique: A binary x_{j,t} for starting job j in period t. Each job
# starts once; a machine-capacity row per period covers the jobs
# spanning it.
#
# On this instance the optimum is 11 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Pritsker, A. A. B., Watters, L. J. and Wolfe, P. M. (1969).
# Multiproject scheduling with limited resources: a zero-one programming
# approach. Management Science 16(1), 93–108.
model m
set J = {1, 2, 3}
set T = {1, 2, 3, 4}
const w = {6, 2, 3}, forall j in J
const p = {1, 1, 1}, forall j in J
bin x, forall j in J, forall t in T
# weighted start time: later starts cost more
min sum_{j in J}{sum_{t in T}{w_{j} * t * x_{j,t}}}
# every job starts exactly once
constr sum_{t in T}{x_{j,t}} = 1, forall j in J
# a job may not start so late that it runs past the horizon
constr sum_{t in T}{[t + p_{j}] * x_{j,t}} <= 5, forall j in J
end
import elytica
Read this through MCP: read with path: "formulations/time-indexed-scheduling", or resource hlpl://formulations/time-indexed-scheduling.