Scheduling


Scheduling -- determine the timing and order of operations to optimize the use of resources to meet production requirements

n jobs 1 machine case

Priority rules (pg.590)

First Come First Serve (FCFS)
Shortest Processing Time (SPT)
Earliest Due Date (EDD)
Slack Time Remaining (STR) = time remaining before due date - remaining processing time
    The shortest STR goes first
Critical Ratio (CR) = Time remaining before due date/Remaining processing time
    The smallest CR goes first
 

Comparison of priority rules

Average Completion time/Mean flow time =(Total processing time + total waiting time)/Number of jobs
Average lateness = total late days/number of jobs
 

Example

Given:
 
Job
Processing time (days)
Due Date (days hence)
Slack time remaining
Critical Ratio
A
20
30
10
1.5
B
30
50
20
1.7
C
10
25
15
2.5
D
16
80
64
5.0
E
18
60
42
3.3

 


 
FCFS
Proc. Time
Flow Time
Due Date
Lateness
A
20
20
30
0
B
30
50
50
0
C
10
60
25
35
D
16
76
80
0
E
18
94
60
34
Total
94
300
245
69
Mean
60
13.8


 
SPT
Proc.
Flow
Time to
Lateness
Seq.
Time
Time
Due
C
10
10
25
0
D
16
26
80
0
E
18
44
60
0
A
20
64
30
34
B
30
94
50
44
Total
94
238
245
78
Mean
47.6
15.6


 
SLACK
Proc.
Flow
Time to
Lateness
Seq.
Time
Time
Due
A
20
20
30
0
C
10
30
25
5
B
30
60
50
10
E
18
78
60
18
D
16
94
80
14
Total
94
282
245
47
Mean
56.4
9.4


 
CR
Proc.
Flow
Time to
Lateness
Seq.
Time
Time
Due
A
20
20
30
0
B
30
50
50
0
C
10
60
25
35
E
18
78
60
18
D
16
94
80
14
Total
94
302
245
67
Mean
60.4
13.4


 
EDD
Proc.
Flow
Time to
Lateness
Seq.
Time
Time
Due
C
10
10
25
0
A
20
30
30
0
B
30
60
50
10
E
18
78
60
18
D
16
94
80
14
Total
94
272
245
42
Mean
54.4
8.4

Comparing the priority rules
 
 
Rule
Mean Flow Time
Mean Lateness
FCFS
60
13.8
SPT
**47.6
15.6
STR
56.4
9.4
CR
60.4
13.4
EDD
54.4
**8.4

Exercises

Pg. 607 Problem 5, 13

Flow shop scheduling

n jobs two machines: all jobs require the same sequence/order in visiting the machines

Johnson's rule

If the shortest time is for the first machine, do the job first
If the shortest time is for the second machine, do the job last
 

Example
 
 
Job
Processing Time, M1
Processing Time, M2
A
5
2
B
3
6
C
8
4
D
10
7
E
7
12

Job sequence: B à E à D à C à A

Gantt Chart representation

Exercises

Pg. 606 Problem 3, 9, 12, 14