Examples

Complete worked examples covering common scheduling and optimisation patterns.

LP: resource allocation

Maximise profit from three products given two resource constraints.

Problem: Produce items A, B, C. Each unit yields profit 5, 4, 3 respectively. Production consumes two resources: Resource 1 (capacity 240) and Resource 2 (capacity 270). Find the production quantities that maximise total profit.

@model lp
model resource_allocation

variables {
  Real: a, b, c
}

domains {
  a in 0..inf
  b in 0..inf
  c in 0..inf
}

constraints {
  6 * a + 4 * b + 2 * c <= 240
  3 * a + 2 * b + 5 * c <= 270
}

maximize 5 * a + 4 * b + 3 * c

CP: job-shop scheduling

A classic 3-job, 2-machine job shop. Each job has two operations that must run in sequence. Each machine can process only one operation at a time. Minimise the time until all jobs are complete (makespan).

model job_shop_3x2

variables {
  Interval: j1_op1, j1_op2
  Interval: j2_op1, j2_op2
  Interval: j3_op1, j3_op2
  Integer: makespan
  Set[Interval]: machine1, machine2
}

domains {
  duration(j1_op1) = 3
  duration(j1_op2) = 2
  duration(j2_op1) = 4
  duration(j2_op2) = 1
  duration(j3_op1) = 2
  duration(j3_op2) = 5

  machine1 = {j1_op1, j2_op2, j3_op1}
  machine2 = {j1_op2, j2_op1, j3_op2}

  makespan in 0..100
}

constraints {
  end_of(j1_op1) <= start_of(j1_op2)
  end_of(j2_op1) <= start_of(j2_op2)
  end_of(j3_op1) <= start_of(j3_op2)

  no_overlap(machine1)
  no_overlap(machine2)

  end_of(j1_op2) <= makespan
  end_of(j2_op2) <= makespan
  end_of(j3_op2) <= makespan
}

minimize makespan

CP: project with phases

A project composed of sequential phases. The span constraint makes the project interval automatically cover all phases. Minimise project completion.

model project_phases

variables {
  Interval: project, design, build, test
  Set[Interval]: phases
}

domains {
  duration(design) = 5
  duration(build)  = 8
  duration(test)   = 3
  phases = {design, build, test}
}

constraints {
  end_of(design) <= start_of(build)
  end_of(build)  <= start_of(test)
  span(project, phases)
}

minimize end_of(project)

The solver will find the earliest possible completion: design at 0–5, build at 5–13, test at 13–16, so end_of(project) = 16.

CP: resource-constrained project scheduling (RCPSP)

Activities with precedence relationships share two limited resources. Each activity consumes a specified amount of each resource while running. The cumulative constraint enforces that the total consumption never exceeds capacity.

model rcpsp_small

variables {
  Interval: a1, a2, a3, a4, a5
  Integer: makespan
  Set[Interval]: res1, res2
}

domains {
  duration(a1) = 3
  duration(a2) = 5
  duration(a3) in 1..4
  duration(a4) = 4
  duration(a5) in {1, 3, 5}

  start(a1, a2) in 0..20
  end(a5) in 0..50

  res1 = {a1, a2, a3}
  res2 = {a1, a3, a4, a5}

  demand(a1, res1) = 2
  demand(a2, res1) = 3
  demand(a3, res1) = 1
  demand(a1, res2) = 1
  demand(a3, res2) = 2
  demand(a4, res2) = 2
  demand(a5, res2) = 1

  makespan in 0..100
}

constraints {
  end_of(a1) <= start_of(a3)
  end_of(a2) <= start_of(a4)
  end_of(a3) <= start_of(a5)

  cumulative(res1, 4)
  cumulative(res2, 3)

  end_of(a5) <= makespan
}

minimize makespan

The variable-duration declarations (in 1..4, in {1, 3, 5}) let the solver choose the duration as part of finding the optimal schedule.