Chapter 16 – Scheduling
16–51
Education.
(d) Job E has the shortest time (4). Because the time for Job E is at Deburring, schedule
Job E toward the end of the sequence (5th). Eliminate Job E from further
consideration.
1st 2nd 3rd 4th 5th 6th 7th
C
B
A
E
D
G
Processing Time
(hours)
Job
Grinding
A
3
B
2
C
1
D
4
E
9
F
8
G
6
1st 2nd 3rd 4th 5th 6th 7th
C
B
A
F
E
D
G
Processing Time
(hours)
Job
Grinding
A
3
B
2
C
1
D
4
E
9
F
8
G
6
Chapter 16 – Scheduling
16–52
Johnson’s
rule
Grinding
Deburring
Job
Start
Finish
Start
Finish
C
0
1
1
6
B
1
3
6
10
A
3
6
10
16
F
6
14
16
23
E
14
23
23
27
D
23
27
27
30
G
27
33
33
35
107
The Grinding flow time is 107 hours, which is 14 hours greater than the flow time for the
SPT sequence (107 – 93 = 14).
The total time (makespan) is 35 hours, which is 2 hours shorter than the SPT makespan (37 –
35 = 2).
d. The tradeoff is between shorter flow time in the Grinding department and shorter total time
(makespan). The production manager would be indifferent concerning the sequences when
the increase in flow time at the Grinding department = the decrease in total time (makespan).
16–53
Education.
15. Given:
We have the following set of jobs in the order of their arrival:
Job
JobTime
(days)
Due Date
(days)
Remaining
Number of
Operations
a
4.5
10
3
b
6.0
17
4
c
5.2
12
3
d
1.6
27
5
e
2.8
18
3
f
3.3
19
1
a. Determine the processing sequence using (1) FCFS, (2) SPT, (3) EDD, and (4) CR. For each
sequence, computer the average tardiness, the average flow time, and the average number of
jobs at the work center:
(1) FCFS Sequence: a-b-c-d-e-f
����� �� ������
Initial critical ratios at day 0:
Job
Processing
Time (Days)
Due Date
(days)
Critical Ratio Calculation
a
4.5
10
(10 – 0) / 4.5 = 2.22
b
6.0
17
(17 – 0) / 6.0 = 2.83
c
5.2
12
(12 – 0) / 5.2 = 2.31
d
1.6
27
(27 – 0) / 1.6 = 16.88
e
2.8
18
(18 – 0) / 2.8 = 6.43
f
3.3
19
(19 – 0) / 3.3 = 5.76
Job a is scheduled first.
Chapter 16 – Scheduling
At day 0 + 4.5 = 4.5 [Job a completed], the critical ratios are:
Job
Processing
Time (Days)
Due Date
(days)
Critical Ratio Calculation
a
—
—
—
b
6.0
17
(17 – 4.5) / 6.0 = 2.08
c
5.2
12
(12 – 4.5) / 5.2 = 1.44
d
1.6
27
(27 – 4.5) / 1.6 = 14.06
e
2.8
18
(18 – 4.5) / 2.8 = 4.82
f
3.3
19
(19 – 4.5) / 3.3 = 4.39
Job c is scheduled next.
Job
Processing
Time (Days)
Due Date
(days)
Critical Ratio Calculation
a
—
—
—
b
6.0
17
(17 – 9.7) / 6.0 = 1.22
c
—
—
—
d
1.6
27
(27 – 9.7) / 1.6 = 10.81
e
2.8
18
(18 – 9.7) / 2.8 = 2.96
f
3.3
19
(19 – 9.7) / 3.3 = 2.82
Job b is scheduled next.
Job
Processing
Time (Days)
Due Date
(days)
Critical Ratio Calculation
a
—
—
—
b
—
—
—
c
—
—
—
d
1.6
27
(27 – 15.7) / 1.6 = 7.06
e
2.8
18
(18 – 15.7) / 2.8 = 0.82
f
3.3
19
(19 – 15.7) / 3.3 = 1.00
Job e is scheduled next.
Chapter 16 – Scheduling
16–55
Education.
At day 15.7 + 2.8 = 18.5 [Job e completed], the critical ratios are:
Job
Processing
Time (Days)
Due Date
(days)
Critical Ratio Calculation
a
—
—
—
b
—
—
—
c
—
—
—
d
1.6
27
(27 – 18.5) / 1.6 = 5.31
e
—
—
—
f
3.3
19
(19 – 18.5) / 3.3 = 0.15
Job f is scheduled next.
Only Job d remains. Job d is scheduled last.
CR Sequence: a-c-b-e-f-d
Performance Measures for each Rule
FCFS:
SPT:
Job
Flow
Due
Days
Job
Flow
Due
Days
Job
time
time
date
tardy
Job
time
time
date
tardy
a
4.5
4.5
10
0
d
1.6
1.6
27
0
b
6.0
10.5
17
0
e
2.8
4.4
18
0
c
5.2
15.7
12
3.7
f
3.3
7.7
19
0
d
1.6
17.3
27
0
a
4.5
12.2
10
2.2
e
2.8
20.1
18
2.1
c
5.2
17.4
12
5.4
f
3.3
23.4
19
4.4
b
6.0
23.4
17
6.4
23.4
91.5
10.2
23.4
66.7
14.0
EDD:
CR:
Job
Flow
Due
Days
Job
Flow
Due
Days
Job
time
time
date
tardy
Job
time
time
date
tardy
a
4.5
4.5
10
0
a
4.5
4.5
10
0
c
5.2
9.7
12
0
c
5.2
9.7
12
0
b
6.0
15.7
17
0
b
6.0
15.7
17
0
e
2.8
18.5
18
0.5
e
2.8
18.5
18
0.5
f
3.3
21.8
19
2.8
f
3.3
21.8
19
2.8
d
1.6
23.4
27
0
d
1.6
23.4
27
0
23.4
93.6
3.3
23.4
93.6
3.3
Chapter 16 – Scheduling
Education.
Average job flow time = Total job flow time / Number of jobs
Avg. Job
Tardiness
Avg. Flow Time
Average
Number
of Jobs
FCFS
10.2/6 =
1.70 days
91.5/6 =
15.25 days
91.5/23.4 =
3.91 jobs
SPT
14.0/6 =
2.33 days
66.7/6 =
11.12 days
66.7/23.4 =
2.85 jobs
EDD
3.3/6 =
0.55 days
93.6/6 =
15.60 days
93.6/23.4 =
4.00 jobs
CR
3.3/6 =
0.55 days
93.6/6 =
15.60 days
93.6/23.4 =
4.00 jobs
b. Using the results from part a, show that the average flow time and the average number of jobs
measures are equivalent for all four sequencing rules:
There are several ways to show this. One is to calculate the ratio of average flow time to
average number of jobs for each rule and then observe that they are equal. Here the ratios are
equal to 3.90.
Ratio
FCFS
15.25/3.91 =
3.90
SPT
11.12/2.85 =
3.90
EDD
15.60/4.00 =
3.90
CR
15.60/4.00 =
3.90
Chapter 16 – Scheduling
16–57
Education.
c. Determine the processing sequence using the S/O rule:
Slack = Time until due date – Remaining time to process
Slack per operation (S/O) = Slack / Number of remaining operations
Job
Job Time
(days)
Due
Date
(days)
Operations
Remaining
Slack
Slack per
Operation
(S/O)
Rank
a
4.5
10
3
10 – 4.5
= 5.5
5.5/3 = 1.83
1
b
6.0
17
4
17 – 6.0
= 11.0
11.0/4 = 2.75
3
c
5.2
12
3
12 – 5.2
= 6.8
6.8/3 = 2.27
2
d
1.6
27
5
27 – 1.6
= 25.4
25.4/5 = 5.08
5
e
2.8
18
3
18 – 2.8
= 15.2
15.2/3 = 5.07
4
f
3.3
19
1
19 – 3.3
= 15.7
15.7/1 = 15.7
6
Chapter 16 – Scheduling
16–58
16. Given:
Job
Remaining
Processing
Time
(days)
Due Date
(days)
Remaining
Number of
Operations
a
5
8
2
b
6
5
4
c
9
10
4
d
7
12
3
e
8
10
2
Slack per operation (S/O) = Slack / Number of remaining operations
Job
Job Time
(days)
Due
Date
(days)
Operations
Remaining
Slack
Slack per
Operation (S/O)
Rank
a
5
8
2
8 – 5
= 3
3/2 = 1.50
4
b
6
5
4
5 – 6
= -1
-1/4 = -0.25
1
c
9
10
4
10 – 9
= 1
1/4 = 0.25
2
d
7
12
3
12 – 7
= 5
5/3 = 1.67
5
e
8
10
2
10 – 8
= 2
2/2 = 1.00
3
Chapter 16 – Scheduling
At hour 2.5+ 3.5 = 6 [Job a completed], the critical ratios are:
Job
Job Time
(hours)
Due Date
(hours)
Critical Ratio Calculation
a
—
—
—
b
2.0
6
(6 – 6) / 2.0 = 0.00
c
4.5
18
(18 – 6) / 4.5 = 2.67
d
5.0
22
(22 – 6) / 5.0 = 3.20
e
—
—
—
f
6.0
20
(20 – 6) / 6.0 = 2.33
Job b is scheduled next.
At hour 6 + 2.0 = 8 [Job b completed], the critical ratios are:
Job
Job Time
(hours)
Due Date
(hours)
Critical Ratio Calculation
a
—
—
—
b
—
—
—
c
4.5
18
(18 – 8) / 4.5 = 2.22
d
5.0
22
(22 – 8) / 5.0 = 2.80
e
—
—
—
f
6.0
20
(20 – 8) / 6.0 = 2.00
At hour 8 + 6.0 = 14 [Job f completed], the critical ratios are:
Job
Job Time
(hours)
Due Date
(hours)
Critical Ratio Calculation
a
—
—
—
b
—
—
—
c
4.5
18
(18 – 14) / 4.5 = 0.89
d
5.0
22
(22 – 14) / 5.0 = 1.60
e
—
—
—
f
—
—
—
Job c is scheduled next.
Only Job d remains. Job d is scheduled last.
CR sequence: e-a-b-f-c-d