CH 15 Production Scheduling
CH 15 Production Scheduling
CH 15 Production Scheduling
Ch 15.1-2
ISE 251
Supplements:
Alharkin, Algorithms for Sequencing and Scheduling
1 Pinedo, Ch 4, Scheduling, 3rd Ed.
The Hierarchy of Production Decisions
Methods:
– Sequencing:
» Gives order of releases but not times.
» Adequate for simple CONWIP lines
where FISFO is maintained.
» The “CONWIP backlog.”
– Scheduling:
» Gives detailed release times.
» Attractive where complex routings make simple sequence impractical.
» MRP/Capacity Planning. 3
Types of Shops
Job Shop
Process 2
Process 4
Process 1
Process 3
Flow Shop
4
Sequencing for Single Machine
ti : processing time
di : due date
Wi : waiting time
Fi : flow time Fi = W i + t i
Li : lateness Li = Fi - di
Ti : tardiness Ti = max[Li,0]
Ei : earliness Ei = max[-Li,0]
Additional
Reference: 5
Alharkan,
Objectives in Job Shop Scheduling
Static or dynamic
8
Example
9
Sequencing Solutions
11
Sequencing Solutions
12
Alharkin, Ch 2
Shortest Processing Time (SPT)
Example
If your goal is to:
Minimize mean flow time
Minimize waiting time
Minimize mean lateness
Use: SPT
Fine grooves with different length and width
need to made in four work pieces with an
ultrasonic machine:
Job Process Due Date
Time
(1) 8 17
(2) 14 53
(3) 27 49
(4) 19 32 13
(5) 3 8
Alharkin, Ch 2
SPT Solution
Sequence: 5, 1, 2, 4, 3
Processing Times:
5 1 2 4 3
Time: 3 11 25 44 71
14
Release/Due Date Related
Current
Time
max d j p j t ,0
Processing
Time
Deadline
15
Alharkin, Ch 2
EDD Solution
s.t.
t j rj j
tti j p j M gyi , j n
(i,j) pairs 2 pairs
ttj i pi M g(1 yi , j )
t j p j d j Lmax j
t j 0 yi , j 0,1 Lmax , M pj
j 17
Alharkin, Ch 2
Sequencing for Single Machine
18
Alharkin, Ch 2
Moore’s Algorithm
New Sequence: 5, 1, 4, 2
Processing Times:
5 1 4 2
Time:
3 11 30 44
No late jobs in this sequence.
Job 3 placed at end. Only one tardy job.
E T
i 1
i
i 1
i
all di = d
no inserted idle time
– once processing begins, jobs continually
scheduled
w 53
i 1
i
• order by non-increasing
wi’+ wi’’
job i 1 2 3 4 5 4,5,2,3,1
b 1 2
•
pi 5 7 4 8 12 32<5 62>5
J1 sum(1,b)
3 3
w i’ 4 8 8 12 15
• WLPT J1 : 5-4 24
wi’’ 7 7 4 20 15
• WSPT J2 : 1-2-3 or 1-3-2
Total Earliness and Tardiness Pinedo, Ch 4
Common “Tight” Due Date
else STOP
Total Earliness and Tardiness Pinedo, Ch 4
Common “Tight” Due Date
Example: d = 15
job i 1 2 3 4 5
pi 5 7 4 8 12
LPT
order k 4 3 5 2 1
5 {4,1,3,2,5}
26
Alharkin, Ch 4
Multiple Machines
Machine 1 1 2
Machine 2 1 2
Time: 2 56 8
29
Alharkin, Ch 4
Classic Multi Machine Results
available position.
If time came from second list, place job in last
Data:
Job Time on M1 Time on M2 List 1 List 2
1 4 9 4 (1) 5 (3)
2 7 10 6 (3) 9 (1)
3 6 5 7 (2) 10 (2)
31
Johnson’s Algorithm Example (cont.)
List 1 List 2
6 (3) 5 (3)
7 (2) 10 (2)
Iteration 2: min time is 5 (job 3 on M3); place this job
last and remove from lists:
32
Gantt Chart for Johnson’s Algorithm
Example
Machine 1 1 2 3
Machine 2 1 2 3
Time 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
33
Alternative Algorithmic Form
Define set U as all jobs with processing time on
machine 1 (t1) < processing time on machine 2
(t2)
– U = {jobs | t1 < t2}
35
Solution
36
Another Example
37
Solution
38
Alharkin, Ch 4
Three Machines
True if either:
min Ai ≥ max Bi or min Ci ≥ max Bi
– (If the second machine is not a bottleneck)
39
Example
40
Machine 2 Bottleneck?
Min Ai = 8
Max Bi = 10
Min Ci = 1
41
Solution
Milling Grinder Polishing
1 15 2 1
2 8 6 14
3 18 2 3
4 25 5 5
5 17 10 20
6 22 10 20
Add t1 and t2 and treat as single machine.
42
Solution
Milling Grinder Polishing
1 15 2 1
2 8 6 14
3 18 2 3
4 25 5 5
5 17 10 20
6 22 10 20
Add t2 and t3 and treat as single machine.
43
Solution
M1’ M2’
1 17 3
2 14 20
3 20 5
4 30 10
5 27 30
6 32 30
44
Solution
M1’ M2’
1 17 3
2 14 20
3 20 5
4 30 10
5 27 30
6 32 30
Order: U={2,5} V={6,4,3,1}
Sequence: 2 5 6 4 3 1
45
Gantt Chart Solution
2 5 6 4 3 1
2 5 6 4 3 1
2 5 6 4 3 1
8 14 25 28 35 45 47 55 57 72 77 82 90 92 95 105 108
107
47
CDS Procedure
TRIAL 1: 1 2 3 4
TRIAL 2: 1 2 3 4
TRIAL 3: 1 2 3 4 48
Example
Trial 1:
Machines
Job 1 2 3 4
1 25 45 52 40
2 7 41 22 66
3 41 55 33 21
4 74 12 24 48
5 7 15 72 52
6 12 14 22 32
49
Example
Trial 2:
Machines
Job 1 2 3 4
1 25 45 52 40
2 7 41 22 66
3 41 55 33 21
4 74 12 24 48
5 7 15 + 72 52 +
6 12 14 22 32
50
Example
Trial 3:
Machines
Job 1 2 3 4
1 25 45 52 40
2 7 41 22 66
3 41 55 33 21
4 74 12 24 48
5 7 15 72 52
6 12 14 22 32
51
Solution
l=1 l=2 l=3
Job Ai,1 Bi,1 Ai,2 Bi,2 Ai,3 Bi,3
1 25 40 70 92 122 137
2 7 66 48 88 70 129
3 41 21 96 54 129 109
4 74 48 86 72 110 84
5 7 52 22 124 94 139
6 12 32 26 54 48 68
Sequences:
256143 562143 625134
Makespans:
335 353 322
52
Flow Shop Scheduling
Calculating permutation schedule job completion
times
– tabular format
– let rows be ordered set of machines
– let columns be the jobs ordered as in the solution
sequence
Opt Seq E A D B C
m1 5 5+6=11 11+9=20 20+11=31 31+7=38
m2 5+10=15 15+8=23 23+7=30 31+6=37 38+3=41
makespa 54
n
Parallel Machine
Alharkin, Ch 3
Scheduling
Situation
m parallel machines
machine
- Identical
…
machine - Nonidentical
n jobs .
.
.
machine
1 n
M * max{ t j , max{t j }}
m j 1
Job 1 2 3 4 5 6 7 8
Processing time 1 2 3 4 5 6 7 8
m 3
36 1 2 3 4 5
M * max{ ,8} 12 5 6 7
3
7 8
3 10
56
Parallel Machine Scheduling
Minimizing makespan (heuristic)
Job 1 2 3 4 5 6 7 8
Processing time 1 2 3 4 5 6 7 8
8 3 2
LPT order: 7 4 1
8 7 6 5 4 3 2 1 6 5
57
13
Alharkin, Ch 3
Parallel Machine Scheduling
Minimizing mean flow time
m 2 5 1 3 2
SPT order: 7 6 8 4
5 7 1 6 3 8 2 4
3 7 21 58
Static Stochastic Scheduling
Practical Worst Case Assumption
Flow Shop
– Johnsons algorithm for scheduling n jobs on two machines in
the deterministic case has a natural extension to the
stochastic case as long as the job times are exponentially
distributed.
Job i before i+1 if
min(Ai,Bi+1) < min(Ai+1,Bi) 60
Johnson’s Stochastic Case
Rates A Rates B
1 1/15 = .0667 .333
2 1/8 = .125 .05
3 .056 .20
4 .04 .125
5 .059 .05
6 .045 .033
63
Example
A B Diff
1 .0667 .333 -.2667
2 .125 .05 .075
3 .056 .20 -.1444
4 .04 .125 -.085
5 .059 .05 .00882
6 .045 .033 .01212
PWC Schedule: 2, 6, 5, 4, 3, 1
64