Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.

Phúc
I. PERT Model
1. Components
❖ Job – Node, Start time: ES/LS Slack: LC – EC or LS – ES
❖ Precedence diagram, Completion time: EC/LC Makespan
❖ Processing time: 𝑝𝑗

2. Precedence diagram
Job Processing Precedence
time
1 5 -
2 4 1
3 6 1
4 10 1, 2
5 8 2
6 5 3, 4
7 11 4, 5, 6
8 7 5, 7

3. Fill the table

ES/EC: Forward.
Find ES = max complete time of predecessor.
Find EC = ES + p
LS/LC: Backward. (Set LC = EC)
Find LC = min start time (LS) of successor.
Find LS = LC – p
Job p ES EC LS LC Slack
1 5 0 5 0 Min (5, 13, 9) = 5 0
2 4 5 9 5 Min (9, 16) = 9 0
3 6 5 11 13 19 8
4 10 max(5,9) = 9 19 9 Min (19, 24) = 19 0
5 8 9 17 16 Min(24, 35) = 24 7
6 5 Max(11,19) = 19 24 19 24 0
7 11 Max(19,17,24) = 24 35 24 35 0
8 7 Max(17, 35) = 35 42 35 42 0

4. Critical path
The path(s) has longest total processing time, and all jobs having Slack = 0
1–2–4–6–7–8

1
Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.Phúc
II. Time-Cost tradeoff
1. Components and concepts
❖ Overhead cost = 𝑐0 × 𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛
Renting machine, Renting land cost, Labor cost
❖ Processing time: Vary in the range of [𝒑𝒎𝒊𝒏 ; 𝒑𝒎𝒂𝒙 ]
At 𝒑𝒎𝒊𝒏
𝒋 the cost is 𝒄𝒂𝒋 , at 𝒑𝒎𝒂𝒙
𝒋 the cost is 𝒄𝒃𝒋 𝒄𝒂𝒋 ≥ 𝒄𝒃𝒋
Cost to reduce processing time of a job by 1 unit of time: 𝛼𝑗
𝑐𝑗𝑎 − 𝑐𝑗𝑏
𝛼𝑗 = 𝑚𝑎𝑥
𝑝𝑗 − 𝑝𝑗𝑚𝑖𝑛
=> To reduce overhead cost, reducing makespan = reducing PT of CP
Rule: cost of reducing PT ≤ overhead cost unit

Minimum cut set: a set of jobs such that satisfy 2 requirements:

- Removing all jobs in the set will disconnect the Source & Sink.
- Putting back 1 arbitrary job in the set will connect the Source & Sink.
*For critical path(s) only. 1 source and 1 sink only.

2. Procedure (𝒄𝟎 = 𝟔)

2
Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.Phúc
Iteration 1: 𝒑𝒋 = 𝒑𝒎𝒂𝒙
𝒋 for all jobs
Job 1 2 3 4 5 6 7 8 9 10 11
ES 0 8 0 0 6 3 3 8 8 13 15
EC 8 13 6 3 8 8 5 12 15 17 24
LS 0 15 0 0 6 3 13 11 8 20 15
LC 8 20 6 3 8 8 15 15 15 24 24
Slack 0 7 0 0 0 0 10 3 0 7 0

- Cmax = 24
- Total overhead cost = 6 x 24 = 144
- Critical paths:
(1 – 9 – 11)
(3 – 5 – 9 – 11)
(4 – 6 – 9 – 11)

- Minimum cut set: {1, 3, 4} , {1, 5, 6} , {1, 3, 6} , {1, 5, 4}, {9}, {11} with
𝛼134 = 𝟏𝟎, 𝛼156 = 𝟏𝟐, 𝛼136 = 𝟏𝟐, 𝛼154 = 𝟏𝟎, 𝛼9 = 𝟒, 𝛼11 = 𝟒
- Best candidate: {9} and {11}
- Saving cost of candidate: 6 – 4 = 2

Iteration 2: Reducing processing time of job 9 by 1 unit

Job 1 2 3 4 5 6 7 8 9 10 11
ES 0 8 0 0 6 3 3 8 8 13 14
EC 8 13 6 3 8 8 5 12 14 17 23
LS 0 14 0 0 6 3 12 10 8 19 14
LC 8 19 6 3 8 8 14 14 14 23 23
Slack 0 6 0 0 0 0 9 2 0 6 0

- Cmax = 23
- Total overhead cost = 6 x 23 = 138
- Critical paths:
(1 – 9 – 11),
(3 – 5 – 9 – 11),
(4 – 6 – 9 – 11)

- Minimum cut set: {1, 3, 4} , {1, 5, 6} , {1, 3, 6} , {1, 5, 4}, {9}, {11} with
𝛼134 = 𝟗, 𝛼156 = 𝟏𝟐, 𝛼136 = 𝟏𝟐, 𝛼154 = 𝟏𝟎, 𝛼9 = 𝟒, 𝛼11 = 𝟒
- Best candidate: {9} and {11}
- Saving cost of candidate: 6 – 4 = 2

3
Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.Phúc
Iteration 3: Reducing processing time of job 9 by 1 unit
Job 1 2 3 4 5 6 7 8 9 10 11
ES 0 8 0 0 6 3 3 8 8 13 13
EC 8 13 6 3 8 8 5 12 13 17 22
LS 0 13 0 0 6 3 11 9 8 18 13
LC 8 18 6 3 8 8 13 13 13 22 22
Slack 0 5 0 0 0 0 8 1 0 5 0

- Cmax = 22
- Total overhead cost = 6 x 22 = 138
- Critical paths: (1 – 9 – 11), (3 – 5 – 9 – 11), (4 – 6 – 9 – 11)
- Minimum cut set: {1, 3, 4} , {1, 5, 6} , {1, 3, 6} , {1, 5, 4}, {9}, {11} with
𝛼134 = 𝟗, 𝛼156 = 𝟏𝟐, 𝛼136 = 𝟏𝟐, 𝛼154 = 𝟏𝟎, 𝛼11 = 𝟒
(𝑝9 = 𝑝9𝑚𝑖𝑛 → no consideration)
- Best candidate: {11}
- Saving cost of candidate: 6 – 4 = 2

Cost = Overhead cost + Cost of reducing processing time

= Co x Makespan (sau khi reduce) + (4 + 4 + 4) = 6 x 21 + 12 = 138

4
Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.Phúc
III. JOB SHOP PROBLEM

Given the following job shop problem, calculate the makespan

Job Sequence Processing Time
1 1,2,3 𝑝11 = 10, 𝑝21 = 8, 𝑝31 = 4
2 2,1,4,3 𝑝22 = 8, 𝑝12 = 3, 𝑝42 = 5, 𝑝32 = 6
3 1,2,4 𝑝13 = 4, 𝑝23 = 7, 𝑝43 = 3

Answer

Total processing time of job 1: 10 + 8 + 4 = 22

Total processing time of job 2: 8 + 3 + 5 + 6 = 22
Total processing time of job 3: 4 + 7 + 3 = 14
𝐶𝑚𝑎𝑥 = 𝟐𝟐

5
Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.Phúc
IV. MATHEMATICAL MODEL

1. Open Facility Decision

𝐶𝑗 : capacity of facility 𝑗
𝑋𝑗 : binary decision variable, = 1 if facility 𝑗 is opened, otherwise 𝑋𝑗 =0
It is often that, there are at least one of 2 following constraints

∑( ) ≤ 𝐶𝑗 × 𝑋𝑗 ∑( ) ≤ 𝐵𝑖𝑔𝑀 × 𝑋𝑗
𝑖 𝑖

Ex: quantity tại facility ≤ capacity * (binary)

Ex: nếu binary = 0 => quantity = 0
Q <= BigM * Xj
2. Binary Inference
If X = 1 then Y = 1: 𝑌≥𝑋
If X = 1 then Y = 0: 𝑌 ≤1−𝑋
If X = 0 then Y = 0: 𝑌≤𝑋
If X = 0 then Y = 1: 𝑌 ≥1−𝑋

3. Inference Condition
If (X = 1) then 𝐴 ≤ 𝐵 𝐵𝑖𝑔𝑀 × (𝑋 − 1) + 𝐴 ≤ 𝐵
If (X = 0) then 𝐴 ≥ 𝐵 𝐵𝑖𝑔𝑀 × 𝑋 + 𝐴 ≥ 𝐵
𝐵𝑖𝑔𝑀 × (𝑋 − 1) + 𝐴 ≤ 𝐵
If (X = 1) then 𝐴 = 𝐵 {
𝐵𝑖𝑔𝑀 × (1 − 𝑋) + 𝐴 ≥ 𝐵
4. Max Constraint
𝑋 = max(𝐴, 𝐵)
Let 𝑌 be the binary variable
1 , 𝑖𝑓 𝐴 − 𝐵 ≥ 0
𝑌={
0 , 𝑖𝑓 𝐴 − 𝐵 ≤ 0
The constraint 𝑋 = max (𝐴, 𝐵) can be transformed to linear form:
𝐵 ≤ 𝑋 ≤ 𝐵 + 𝐵𝑖𝑔𝑀 × 𝑌
{
𝐴 ≤ 𝑋 ≤ 𝐴 + 𝐵𝑖𝑔𝑀 × (1 − 𝑌)

5. Min Constraint
𝑋 = min(𝐴, 𝐵)
Let 𝑌 be the binary variable
1 , 𝑖𝑓 𝐴 − 𝐵 ≥ 0
𝑌={
0 , 𝑖𝑓 𝐴 − 𝐵 ≤ 0
The constraint 𝑋 = min (𝐴, 𝐵) can be transformed to linear form:

6
Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.Phúc
𝐵 ≥ 𝑋 ≥ 𝐵 − 𝐵𝑖𝑔𝑀 × (1 − 𝑌)
{
𝐴 ≥ 𝑋 ≥ 𝐴 − 𝐵𝑖𝑔𝑀 × 𝑌
6. ‘And’ Condition
Given 𝑋𝑖 , 𝑌 are binary variables. 𝑌 relates to 𝑋𝑖 through ‘And’ operator
𝑌 = 𝑋1 ∩ 𝑋2 ∩ 𝑋3 … ∩ 𝑋𝑛
This constraint can be transformed to linear form as
𝑌 ≤ 𝑋𝑖 , ∀𝑖, 𝑖 = 1 … 𝑛
{
𝑌 ≥ Σ𝑖 𝑋𝑖 − 𝑛 + 1

7. ‘Or’ Condition
Given 𝑋𝑖 , 𝑌 are binary variables. 𝑌 relates to 𝑋𝑖 through ‘Or’ operator
𝑌 = 𝑋1 ∪ 𝑋2 ∪ 𝑋3 … ∪ 𝑋𝑛
This constraint can be transformed to linear form as
𝑌 ≥ 𝑋𝑖 , ∀𝑖, 𝑖 = 1 … 𝑛
{
𝑌 ≤ Σ𝑖 𝑋𝑖
Example:
The company wants to maximize the benefit of a project:
- If they manufacture type A, they have to buy at least 𝑛1 type 1 PL.
- If they manufacture type B, they have to buy at least 𝑛2 type 2 PL
- If item A is not manufactured, then the # of type 1 production lines is .
- If item B is not manufactured, then the # of type 2 production lines is 0.
- If they decide to manufacture both A and B, they have to open the DC D .
- If either A or B is manufactured, then they have to hire a 3rd party G.
Parameters
𝑐1 : cost for buy one type 1 production line
𝑐2 : cost for buy one type 2 production line
𝑛1 : minimum number of type 1 PL for manufacturing type A
𝑛2 : minimum number of type 2 PL for manufacturing type B
𝑐𝐷 : cost for open and operation of distribution center D
𝑐𝐺 : cost for hire the logistics service G during the planning horizon
𝑏𝐴 : benefit if item A is produced during the planning horizon
𝑏𝐵 : benefit if item B is produced during the planning horizon
Decision variables
𝑥𝐴 , 𝑥𝐵 , 𝑥𝐷 , 𝑥𝐺 : binary variablehired, otherwise 0
𝑌1 : number of production line type 1
𝑌2 : number of production line type 2

7
Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.Phúc
ANSWER
Objective: Maximize Z = 𝑏𝐴 𝑋𝐴 + 𝑏𝐵 𝑋𝐵 − 𝑐1 𝑌1 − 𝑐2 𝑌2 − 𝑐𝐷 𝑋𝐷 − 𝑐𝐺 𝑋𝐺
Subject to

Inference condition 𝐵𝑖𝑔𝑀 × (𝑋𝐴 − 1) + 𝑛1 ≤ 𝑌1

𝐵𝑖𝑔𝑀 × (𝑋𝐵 − 1) + 𝑛2 ≤ 𝑌2
𝑌1 ≤ 𝑋𝐴 × 𝐵𝑖𝑔𝑀
Open facility decision
𝑌2 ≤ 𝑋𝐵 × 𝐵𝑖𝑔𝑀
𝑋𝐷 ≤ 𝑋𝐴
‘And’ condition 𝑋𝐷 ≤ 𝑋𝐵
𝑋𝐷 ≥ (𝑋𝐴 + 𝑋𝐵 ) − 2 + 1
𝑋𝐺 ≥ 𝑋𝐴
‘Or’ condition 𝑋𝐺 ≥ 𝑋𝐵
𝑋𝐺 ≤ (𝑋𝐴 + 𝑋𝐵 )
Practice
We need to construct a product planning for J jobs j=1…J in 28 days, d=1…28. Minimize the total
cost using following annotations
Parameters
𝑝𝑗 : processing time of job 𝑗
𝑎: cost of one unit of overtime
𝐻𝑚𝑎𝑥 : maximum number of hours in one day can used for manufacturing
𝐻𝑑𝑒𝑓𝑎𝑢𝑙𝑡 : default number of hours in one day can be used for manufacturing
Decision variables
𝑋𝑗𝑑 : binary variable, 𝑋𝑗𝑑 = 1 if job 𝑗 is manufactured in day 𝑑; otherwise
𝑂𝑑 : # of total overtime in day 𝑑 that the company has to pay the cost

Following requirements must be satisfied.

• One job must be assigned to one day and must be finished within that day
• The total working time in a day must smaller than 𝐻𝑚𝑎𝑥
• In normal day, when the total working time in that day is higher than 𝐻𝑑𝑒𝑓𝑎𝑢𝑙𝑡 and
smaller than 𝐻𝑚𝑎𝑥 , it will incur some cost based on the difference between total
working time and 𝐻𝑑𝑒𝑓𝑎𝑢𝑙𝑡

8
Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.Phúc
a) Assume that all day are normal days, make the model for this problem
Introduce new variable
𝑍𝑑 : binary, 𝑍𝑑 = 1 if ∑𝑗 𝑝𝑗 𝑋𝑗𝑑 ≥ 𝐻𝑑𝑒𝑓𝑎𝑢𝑙𝑡 , otherwise 𝑍𝑑 = 0
Minimize ∑𝑑 𝑎 × 𝑂𝑑
Subject to
∑ 𝑋𝑗𝑑 = 1 ∀𝑗
𝑑

∑ 𝑝𝑗 𝑋𝑗𝑑 ≤ 𝐻𝑚𝑎𝑥 ∀𝑑
𝑗

If 𝑍𝑑 = 1, then 𝐻𝑑𝑒𝑓𝑎𝑢𝑙𝑡 ≤ ∑𝑗 𝑝𝑗 𝑋𝑗𝑑 𝐵𝑖𝑔𝑀 × (𝑍𝑑 − 1) + 𝐻𝑑𝑒𝑓𝑎𝑢𝑙𝑡 ≤ ∑ 𝑝𝑗 𝑋𝑗𝑑 ∀𝑑

𝑗
If 𝑍𝑑 = 0, then 𝐻𝑑𝑒𝑓𝑎𝑢𝑙𝑡 ≥ ∑𝑗 𝑝𝑗 𝑋𝑗𝑑
𝐵𝑖𝑔𝑀 × (𝑍𝑑 ) + 𝐻𝑑𝑒𝑓𝑎𝑢𝑙𝑡 ≥ ∑ 𝑝𝑗 𝑋𝑗𝑑 ∀𝑑
𝑗

𝐵𝑖𝑔𝑀 × (𝑍𝑑 − 1) + 𝑂𝑑 ≤ ∑ 𝑝𝑗 𝑋𝑗𝑑 − 𝐻𝑑𝑒𝑓𝑎𝑢𝑙𝑡 ∀𝑑

If 𝑍𝑑 = 1, then
𝑗
𝑂𝑑 = ∑𝑗 𝑝𝑗 𝑋𝑗𝑑 − 𝐻𝑑𝑒𝑓𝑎𝑢𝑙𝑡 𝐵𝑖𝑔𝑀 × (1 − 𝑍𝑑 ) + 𝑂𝑑 ≥ ∑ 𝑝𝑗 𝑋𝑗𝑑 − 𝐻𝑑𝑒𝑓𝑎𝑢𝑙𝑡 ∀𝑑
𝑗
If 𝑍𝑑 = 0, then 𝑂𝑑 = 0 𝑂𝑑 ≤ 𝐵𝑖𝑔𝑀 × 𝑍𝑑 ∀𝑑

b) Assume that on weekend, ie days 6, 7, 13, 14, 20, 21, 27, 28, the total overtime in day 𝑑 is
equal to the total working time in that day. Modify model in part a) to fix with this adjustment
Explanation:
Overtime on normal day = 𝑂𝑑 = max (𝑝𝑗 × 𝑋𝑗𝑑 – 𝐻𝑑𝑒𝑓𝑎𝑢𝑙𝑡 , 0)
Overtime on weekend = 𝑝𝑗 × 𝑋𝑗𝑑

Define all days set D

Define weekend set W = {6, 7, 13, 14, 20, 21, 27, 28}
Define normal set N = the rest = {1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 15, 16, 17, 18, 19, 22, 23, 24, 25, 26}

𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑎 (∑ 𝑂𝑑 + ∑ 𝑝𝑗 × 𝑋𝑗𝑑 )
𝑑∈𝑁 𝑑∈𝑊

Subject to

∑ 𝑋𝑗𝑑 = 1 ∀𝑗
𝑑∈𝐷

∑ 𝑝𝑗 𝑋𝑗𝑑 ≤ 𝐻𝑚𝑎𝑥 ∀𝑑 ∈ 𝐷
𝑗

9
Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.Phúc

𝐵𝑖𝑔𝑀 × (𝑍𝑑 − 1) + 𝐻𝑑𝑒𝑓𝑎𝑢𝑙𝑡 ≤ ∑ 𝑝𝑗 𝑋𝑗𝑑 ∀𝑑 ∈ 𝑁

𝑗

𝐵𝑖𝑔𝑀 × (𝑍𝑑 ) + 𝐻𝑑𝑒𝑓𝑎𝑢𝑙𝑡 ≥ ∑ 𝑝𝑗 𝑋𝑗𝑑 ∀𝑑 ∈ 𝑁

𝑗

𝐵𝑖𝑔𝑀 × (𝑍𝑑 − 1) + 𝑂𝑑 ≤ ∑ 𝑝𝑗 𝑋𝑗𝑑 − 𝐻𝑑𝑒𝑓𝑎𝑢𝑙𝑡 ∀𝑑 ∈ 𝑁

𝑗

𝐵𝑖𝑔𝑀 × (1 − 𝑍𝑑 ) + 𝑂𝑑 ≥ ∑ 𝑝𝑗 𝑋𝑗𝑑 − 𝐻𝑑𝑒𝑓𝑎𝑢𝑙𝑡 ∀𝑑 ∈ 𝑁

𝑗

𝑂𝑑 ≤ 𝐵𝑖𝑔𝑀 × 𝑍𝑑 ∀ 𝑑 ∈ 𝑁

10
Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.Phúc
V. CODE CPLEX
• Declare the size of set (int)
• Declare the range of each index (range)
• Declare the parameters (float, int)
• Declare the decision variable (dvar type: float, float+, int, int+, boolean)
• Objective function (maximize, minimize)
• Constraint (forall, sum, …)
How to use Tuple?
- Define the tuple
tuple tupleName{
dataType attribute1;
dataType attribute2;
}
- Create the sets corresponding to tuple
setof (tupleName) tupleSet = …;
- Read parameters which use tuple as index
float ParameterA [tupleSet] = …;
- Declare the decision variables which use tuple as index
dvar boolean X[tupleSet];
Example 1
1. Size and range
𝑖: index of the item type
2. Parameters
𝐵𝑖 : the benefit of an item type 𝑖
𝑊𝑖 : the weight of an item type 𝑖
𝑛𝑖 : the maximum quantity of item type 𝑖
𝐶𝑎𝑝: maximum capacity of the system
3. Decision variable
𝑋𝑖 : the number of item type 𝑖 is adopted
4. Objective function
max 𝑍 = ∑ 𝐵𝑖 𝑋𝑖
𝑖

11
Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.Phúc
5. Constraint
0 ≤ 𝑋𝑖 < 𝑛𝑖 ∀ 𝑖 ∈ 𝑇𝑦𝑝𝑒

∑ 𝑊𝑖 𝑋𝑖 ≤ 𝐶𝑎𝑝
𝑖

ANSWER
int numbType = ...;
range Type = 1..numbType;

float B[Type] = …;
float W[Type] = …;
float n[Type] = …;
float Cap = …;

dvar int+ X[Type];

maximize sum (i in Type) B[i]*X[i];

subject to {
forall (i in Type) {
X[i] < n[i];
X[i] >= 0;
}
sum(i in Type) W[i] * X[i] <= Cap;
}

12
Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.Phúc
Example 2:
Index
t= 1..T: index of tanks
l = 1..L: index of lots of harvested grapes
Parameters
𝐶𝑡 : capacity (tons) of tank 𝑡
𝑃𝑡 = 1 if tank 𝑡 is proscibed from use in certain fermentations, 0 otherwise;
𝑆𝑡 : setup cost incurred each time tank 𝑡 is used;
𝐴𝑙 : expected amount (tons) of lot 𝑙;
𝐻𝑙 : expected harvest date, measured in days from the start of the season of lot 𝑙;
𝐹𝑙 : expeccted fermentation length (days) of lot 𝑙;
𝑅𝑙 : =1 if lot 1 is intedended to become a red wine,
𝑊: user-specified objective weight, where 0 ≤ 𝑊 ≤ 1
𝑀𝑙1,𝑙2 : conflict matrix 𝑀𝑙1,𝑙2 =1 if (𝐻𝑙1 + 𝐹𝑙1 ≥ 𝐻𝑙2 or 𝐻𝑙1 ≤ 𝐻𝑙2 and 𝑙1 ≠ 𝑙2 ),
0 otherwise. In short, it is given and is calculated from other parameters.
Variables
𝑣𝑙,𝑡 : volume of lot 𝑙 assigned to tank 𝑡;
𝑤𝑙,𝑡 : wasted space in tank 𝑡 leftover from being used for lot 𝑙;
𝑚𝑙,𝑡 = 1 if lot 𝑙 is matched to tank t, 0 otherwise;
Objective function

𝑀𝑖𝑛 𝑊 ∑ ∑ 𝑆𝑡 𝑚𝑙,𝑡 + (1 − 𝑊) ∑ ∑ 𝑤𝑙,𝑡

𝑡 𝑙 𝑡 𝑙

Subject to

∑ 𝐶𝑡 𝑚𝑙,𝑡 ≥ 𝐴𝑙 ∀ 𝑙 ∈ 𝐿
𝑡

∑ 𝑣𝑙,𝑡 = 𝐴𝑙 ∀𝑙 ∈ 𝐿
𝑡

𝐶𝑡 𝑚𝑙,𝑡 = 𝑣𝑙,𝑡 + 𝑤𝑙,𝑡 ∀𝑙 ∈ 𝐿, ∀𝑡∈ 𝑇

𝑚𝑙1,𝑡 + 𝑚𝑙2,𝑡 ≤ 1 ∀ 𝑡 ∈ 𝑇, ∀ 𝑙1 ∈ 𝐿, ∀ 𝑙2 ∈ 𝐿, 𝑀𝑙1,𝑙2 = 1

∑ 𝑅𝑙 𝑚𝑙,𝑡 = 0 ∀ 𝑡 ∈ 𝑇, 𝑃𝑡 = 1
𝑙

ANSWER
int T =...;
int L =...;

13
Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.Phúc

range tank = 1..T;

range lot = 1..L;

float C[tank] =…;

int P[tank] =…;
float S[tank] =…;
float A[lot] =…;
int H[lot] =…;
int F[lot] =…;
int R[lot] =…;
float W =…;
int M[lot][lot] =…;

dvar float+ v[lot][tank];

dvar float+ w[lot][tank];
dvar boolean m[lot][tank];

minimize W*sum(t in tank, l in lot)S[t]*m[l][t] + (1-W)*sum(l in lot, t in tank) w[l][t];

subject to {
forall (l in lot) {
sum (t in tank) C[t]*m[l][t] >= A[l];
sum (t in tank) v[l][t]==A[l];
}
forall (l in lot, t in tank) {
C[t]*m[l][t] == v[l][t]+w[l][t];
}
forall (t in tank, l1 in lot, l2 in lot: M[l1][l2]==1) {
m[l1][t] + m[l2][t] <= 1;
}
forall (t in tank: P[t] ==1) {
sum(l in lot) R[l]*m[l][t] == 0;
}
}

14
Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.Phúc

Practice
Index
𝑗: index of job
𝑤: index of worker
𝑏: index of batch
<𝑤, 𝑏> tuple indicating which batch 𝑏 can be handled by worker 𝑤 <𝑤, 𝑏> ∈ 𝐴
<𝑗, 𝑏> tuple indicating which job 𝑗 can be handled by batch 𝑏 < 𝑗, 𝑏 > ∈ 𝐵
Parameter
𝑝𝑗 : processing time of job 𝑗
𝐵𝑖𝑔𝑀: very large number
𝐶𝑎𝑝: working time per shift
Decision variables
𝐻𝑚𝑎𝑥 : The largest completion time of all workers
𝐻𝑚𝑖𝑛 : The smallest completion time of all workers
𝑋<𝑗,𝑏> : binary variable, 𝑋<𝑗,𝑏> = 1 if job 𝑗 is assigned to batch 𝑏 otherwise 𝑋<𝑗,𝑏> = 0
𝑈𝑏 : binary variable, 𝑈𝑏 = 1 if at least one job is assigned to batch 𝑏, otherwise 𝑈𝑏 = 0
𝑇𝑏 : processing time of batch 𝑏
𝑊<𝑤,𝑏> : binary variable, 𝑊<𝑤,𝑏> =1 if worker 𝑤 handles batch 𝑏, otherwise 𝑊<𝑤,𝑏> = 0
𝑍<𝑤,𝑏> : processing time of worker 𝑤 for batch 𝑏
𝐻𝑤 : total processing time worker 𝑤 per shift
𝑅𝑤 : binary variable, 𝑅𝑤 = 1 if worker 𝑤 on board, otherwise 𝑅𝑤 = 0

Objective function
Minimize 𝐻𝑚𝑎𝑥 − 𝐻𝑚𝑖𝑛
Constraints
𝐵𝑖𝑔𝑀(1 − 𝑅𝑤 ) + 𝐻𝑚𝑎𝑥 ≥ 𝐻𝑤 ∀𝑤 ∈ 𝑊
𝐵𝑖𝑔𝑀(𝑅𝑤 − 1) + 𝐻𝑚𝑖𝑛 ≤ 𝐻𝑤 ∀𝑤 ∈ 𝑊
𝑅𝑤 ≥ 𝑊<𝑤,𝑏> ∀ < 𝑤, 𝑏 > ∈ 𝐴

𝑅𝑤 ≤ ∑ 𝑊<𝑤,𝑏> ∀𝑤 ∈ 𝑊
<𝑤,𝑏> ∈ 𝐴

∑ 𝑋<𝑗,𝑏> = 1 ∀𝑏
<𝑗,𝑏> ∈ 𝐵

15
Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.Phúc
𝐻𝑤 ≤ 𝐶𝑎𝑝 ∀𝑤

∑ 𝑊<𝑤,𝑏> = 1 ∀𝑏
<𝑤,𝑏> ∈ 𝐴

𝑇𝑏 = ∑ 𝑋<𝑗,𝑏> × 𝑝𝑗 ∀𝑏
<𝑗,𝑏> ∈ 𝐵

𝑍<𝑤,𝑏> ≤ 𝐵𝑖𝑔𝑀 × 𝑊<𝑤,𝑏> ∀ < 𝑤, 𝑏 > ∈ 𝐴

𝑍<𝑤,𝑏> ≤ 𝑇𝑏 + 𝐵𝑖𝑔𝑀 × (1 − 𝑊<𝑤,𝑏> ) ∀ < 𝑤, 𝑏 > ∈ 𝐴
𝑍<𝑤,𝑏> ≥ 𝑇𝑏 − 𝐵𝑖𝑔𝑀 × (1 − 𝑊<𝑤,𝑏> ) ∀ < 𝑤, 𝑏 > ∈ 𝐴

𝐻𝑤 = ∑ 𝑍<𝑤,𝑏> ∀𝑤
<𝑤,𝑏>∈𝐴

𝑈𝑏 ≥ 𝑋<𝑗,𝑏> ∀ < 𝑗, 𝑏 > ∈ 𝐵

𝑈𝑏 ≤ ∑ 𝑋<𝑗,𝑏> ∀𝑏
<𝑗,𝑏> ∈ 𝐵

ANSWER
int J = …;
int W = …;
int B = …;
tuple WorkerBatch {
int Worker;
int Batch;
}
tuple JobBatch {
int Job;
int Batch;
}

range Job = 1..J;

range Worker = 1..W;
range Batch = 1..B;
setof (WorkerBatch) WorkerBatchSet =…;
setof (JobBatch) JobBatchSet = …;

float p[Job]=…;
16
Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.Phúc
float BigM =…;
float Cap =…;

dvar float+ Hmax;

dvar float+ Hmin;
dvar boolean X[JobBatchSet];
dvar boolean U[Batch];
dvar float+ T[Batch];
dvar boolean W[WorkerBatchSet];
dvar float+ Z[WorkerBatchSet];
dvar float+ H[Worker];
dvar boolean R[Worker];

minimize Hmax – Hmin;

subject to {
forall (w in Worker) {
BigM*(1 - R[w]) + Hmax >= H[w];
BigM*(R[w] - 1) + Hmin <= H[w];
}
forall (<w,b> in WorkerBatchSet) {
R[w] >= W[<w,b>];
}
forall (w in Worker) {
R[w] <= Sum (<w,b> in WorkerBatchSet) W[<w,b>];
}
forall (b in Batch) {
sum (<j,b> in JobBatchSet) X[<j,b>] == 1;
}
forall (w in Worker) {
H[w] <= Cap;
}
forall (b in Batch) {
sum (<w,b> in WorkerBatchSet) W[<w,b>] == 1;
T[b] == sum(<j,b> in JobBatchSet) X[<j,b>] * p[j];
}

17
Scheduling and Sequencing – Mỹ Dung. Reference: Dr. P.N.K.Phúc
forall (<w,b> in WorkerBatchSet) {
Z[<w,b>] <= BigM * W[<w,b>];
Z[<w,b>] <= T[b] + BigM * (1 – W[<w,b>]);
Z[<w,b>] >= T[b] - BigM * (1 – W[<w,b>]);
}
forall (w in Worker) {
H[w] == sum(<w,b> in WorkerBatchSet) Z[<w,b>];
}
forall (<j,b> in JobBatchSet) {
U[b] >= X[<j,b>];
}
forall (b in Batch) {
U[b] <= sum(<j,b> in JobBatchSet) X[<j,b>];
}
}

18