Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 38 ยท Scheduling and Queueing

Scheduling with MILP

Model parallel-machine and single-machine scheduling as MILPs: assignment variables, makespan, disjunctive big-M ordering constraints, time-indexed ideas, compared with LPT and Smith's rule.

Dispatch rules (Scheduling Basics and Dispatch Rules) are optimal for a handful of textbook cases. Once you add parallel machines, release times, setup times or resource limits, you need a more general tool. Mixed-integer programming is the standard one: it models the sequencing decisions with binary variables and lets a solver search for a provably optimal schedule.

This lesson shows the two basic modeling styles: assignment formulations (who runs where) and disjunctive or positional formulations (what comes before what). You will use the patterns from Binary Variables and Logic, especially big-M.

Parallel machines: minimize the makespan

Given n jobs with processing times p_j and m identical machines, assign every job to one machine so that the latest-finishing machine finishes as early as possible. Let x_jk = 1 if job j goes to machine k, and C be the makespan:

TEXT
minimize    C
subject to  sum_k x_jk = 1                 for each job j
            sum_j p_j x_jk <= C            for each machine k
            x_jk in {0, 1}

This is the classic NP-hard load balancing (bin-packing-like) problem. A fast heuristic is LPT (longest processing time first): sort jobs by decreasing p_j and always give the next job to the least loaded machine. LPT is never worse than 4/3 - 1/(3m) times the optimum, and it is often optimal.

Python Optimal makespan with milp versus the LPT heuristic

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

LPT gives 25, but the MILP finds 24, which is provably optimal because the trivial bound ceil(sum p / m) = 24 is a lower bound for any schedule. This model has symmetry: swapping two machines gives an equivalent solution, which hurts bigger instances. Adding load_1 >= load_2 >= load_3 (ordering the machines) removes it.

Single machine: disjunctive formulation

When the order matters, use start times s_j and a binary variable y_ij for each pair of jobs: y_ij = 1 if job i precedes job j. Two jobs on one machine cannot overlap, so either i finishes before j starts or j finishes before i starts, an either-or constraint with big-M:

TEXT
s_j >= s_i + p_i - M (1 - y_ij)
s_i >= s_j + p_j - M y_ij

With M = sum p_j (a valid bound on any start time), exactly one of the two inequalities is enforced. The objective for total weighted completion time is sum w_j (s_j + p_j).

Python Disjunctive MILP versus Smith's rule

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The MILP and Smith's rule reach the same objective, 179. The orders differ only in the swapped pair of jobs 0 and 2, which tie (both have p/w = 2), so both are optimal. This confirms both the formulation and the rule. The MILP is much more flexible: you can now add release times (s_j >= r_j), due dates, sequence-dependent setups or precedence constraints, none of which Smith's rule handles.

A bad big-M is the usual reason scheduling models are slow. Use the tightest bound you can justify, for example the sum of the processing times plus the latest release time, and never 1e6. See Cutting Planes and Formulation Strength.

Other formulations

  • Positional (assignment-based): z_jk = 1 if job j is in position k; then completion times follow from sums of processing times. It avoids big-M but needs n^2 variables.
  • Time-indexed: x_jt = 1 if job j starts at time t within a horizon H. It has a very tight LP relaxation, handles almost any cost function and resource constraint, but its size grows with n * H.
  • Precedence-based (flow-shop and job-shop): y_ij for every pair on each machine plus machine routing constraints. Job-shop problems are famously hard: even 10 jobs by 10 machines can resist solvers, which is why metaheuristics and constraint programming are popular there.

Modeling checklist

  1. List decisions: assignment, sequence, start time.
  2. Choose the formulation family (assignment, disjunctive, positional, time-indexed).
  3. Write the objective with auxiliary variables (C_max, C_j, T_j >= C_j - d_j, T_j >= 0).
  4. Tighten big-M, break symmetry, and set a time limit and gap.
  5. Compare with a simple heuristic (LPT, EDD, Smith) as a sanity check and a warm start.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the parallel-machine makespan MILP, what does the constraint sum_j p_j x_jk <= C say?

    C is bounded below by every machine's total load; minimizing C minimizes the heaviest load.
  2. 2. What does y_ij = 1 mean in a disjunctive formulation?

    y_ij decides the order of the pair; the big-M constraints enforce no overlap in either case.
  3. 3. Why is a very large big-M harmful?

    With a huge M the binary variable can be fractional with almost no effect, which gives poor bounds.
  4. 4. Which formulation has an especially tight LP relaxation but grows with the time horizon?

    Time-indexed models use one binary variable per job and start time; they are strong but large.

Summary

  • MILP handles scheduling features dispatch rules cannot: parallel machines, release dates, setups and extra constraints.
  • Assignment variables with a makespan variable model load balancing; LPT is a strong heuristic benchmark.
  • Disjunctive constraints with binary order variables and big-M forbid overlap on a machine.
  • Tight big-M values, symmetry breaking and time limits keep models solvable.
  • Positional and time-indexed formulations trade size against relaxation strength.

Next: Queueing Fundamentals and the M/M/1 Queue