LeMIE350F
© J. Christopher Beck 2020
1
Lecture 7:
MIP Models for Scheduling
1
© J. Christopher Beck 2020
2
Outline
Time-indexed Formulation for JSP
Disjunctive Formulation for JSP
2
© J. Christopher Beck 2020
3
Readings
Presentations by Stefan Heinz & Timo
Berthold, Zuse Institute Berlin
Applegate & Cook, A Computational
Study of the Job-Shop Scheduling
Problem, ORSA Journal on Computing,
3(2), 149-156, 1991
Ku & Beck, Revisiting Off-the-Shelf
Mixed Integer Programming and
Constraint Programming Models for
Job Shop Scheduling,
Computers & Operations Research,
73, 165-173, 2016
3
Song_dynasty_11th_century_National_Palace_Museum_Taipei_001
MILP Basics
4
Objective function
Constraints
Could be ≤, =, or ≥
Integer variables
Continuous variables
Continuous (linear) relaxation:
poly-time soluble!
© J. Christopher Beck 2020
5
© J. Christopher Beck 2020
Job Shop Scheduling
makespan
6
© J. Christopher Beck 2020
6
Where Do We Start?
Time-Indexed MIP
The main decision variable represents whether a job starts at time t or not
Variables are “indexed” by time
© J. Christopher Beck 2020
8
Notation
Set of time points defined by t and j
What Constraints Do We Need?
Time-Indexed JSP MIP
10
All operations start only once
Cmax is the largest end-time
Precedence constraints
Resource constraints
© J. Christopher Beck 2020
© J. Christopher Beck 2020
11
t = 10
k = blue
A3
A2
A1
… x15 x16 x17 x18 x19 x1,10…
… x25 x26 x27 x28 x29 x2,10…
… x35 x36 x37 x38 x39 x3,10…
Goal: Make sure we are not
over-capacity on the
blue resource at t = 10
p1 = 5
p2 = 3
p3 = 6
Time-Indexed JSP MIP
12
All activities start only once
Cmax is the largest end-time
Precedence constraints
Resource constraints
Questions?
© J. Christopher Beck 2020
12
Disjunctive MIP
The main decision variable represents the sequence between each pair of operations
A before B or B before A
© J. Christopher Beck 2020
13
Notation
What Constraints Do We Need?
Disjunctive JSP MIP
15
Cmax is the largest end-time
Precedence constraints
Resource constraints
© J. Christopher Beck 2020
zji = 1 operation i is after operation j
Sj ≥ Si + pi – M: redundant since Sj ≥ 0
Si ≥ Sj + pj – M×0: precedence constraint
zji = 0 operation j is after operation i
Sj ≥ Si + pi – M×0: precedence constraint
Si ≥ Sj + pj – M: redundant since Si ≥ 0
© J. Christopher Beck 2020
16
Disjunctive JSP MIP
17
Cmax is the largest end-time
Precedence constraints
Resource constraints
Questions?
© J. Christopher Beck 2020
18
© J. Christopher Beck 2020
Which is Best?
19
Results with CPLEX (default parameters)
© J. Christopher Beck 2020
So is time-indexed
useless?
What Happened Today?
MIP models for JSP
Time-indexed model
Disjunctive model
© J. Christopher Beck 2020
20
/docProps/thumbnail.jpeg