Solutions for Chapter 8
Solutions to Problems From Chapter 8
8.4
FCFS
Sequence
Completion Time
1
2
3
4
Flow Time
1:20
1:34
2:09
2:19
20
34
69
79
Total
202
Tardiness
0
0
19
49
68
Mean flow time = 202/4 = 50.5
Average tardiness = 68/4 = 17
Number of tardy trucks = 2
SPT
Truck
Completion Time
4
2
1
3
Flow Time
1:10
1:24
1:44
2:19
Tardiness
10
24
44
79
0
0
19
29
157
48
Flow Time
20
30
44
79
Tardiness
0
0
0
29
Total
Mean flow time = 157/4 = 39.25
Average tardiness = 48/4 = 12
Number of tardy trucks = 2
EDD
Truck
1
4
2
3
Unloading
Time
20
10
14
35
Completion
Time
1:20
1:30
1:44
2:19
Total
173
Mean flow time = 173/4 = 43.25
Average tardiness = 29/4 = 7.25
175
29
Production and Operations Analysis, Fourth Edition
Number of tardy trucks = 1
CR
Time: 1:00 p.m:
Truck
Unloading Time
1
20
2
14
3
35
4
10
Time: 1:20 p.m:
Truck
2
25/14
3
35/30
4
10/10
Time:
Truck
2
4
Due Time
25
45
50
30
25/20
45/14
50/35
30/10
CR
= 1.25*
= 3.21
= 1.43
= 3.0
CR
= 1.79
= 1.17*
= 1
1:55 p.m:
CR
-10/14 <0
-25/10 <0
1-3-4-2
Summary for the results for the CR Scheduling
Truck
Unloading Time
Completion Time
Flow Time
20
35
10
14
1:20
1:55
2:05
2:19
20
55
65
79
Tardiness
1
3
4
2
Totals
219
0
5
35
34
74
Mean flow time = 219/4 = 54.75
Average tardiness = 74/4 = 18.5
Number of tardy trucks = 3
8.5
Scheduling by SPT means that the jobs are processed in the sequence 3-1-5-2-4.
SPT Sequencing
Job
Processing
Time
Completion Time
20 min.
10:20 a.m.
Promised Time
Tardiness(hrs)
176
2:00 p.m.
Solutions for Chapter 8
1
5
2
4
40
1.5
2.5
4
min.
hrs.
hrs.
hrs.
11:00
12:30
3:00
7:00
a.m.
p.m.
p.m.
p.m.
11:00
4:00
2:00
1:00
a.m
p.m.
p.m.
p.m
0
0
1
6
Mean tardiness = 7/5 hrs. = 1.4 hours.
The EDD sequence is 1-4-2-3-5 (or 1-4-3-2-5).
EDD Sequencing
Job
Processing
Time
Completion Time
Promised Time
Tardiness(hrs)
1
4
2
3
5
40
4
2.5
20
1.5
min.
hrs.
hrs.
min.
hrs
10:40
2:40
5:10
5:30
7:00
a.m.
p.m.
p.m.
p.m.
p.m.
11:00
1:00
2:00
2:00
4:00
Mean tardiness = 2.265 hrs.
8.7
Lawlers algorithm
1
4
6
Job
1
2
3
4
5
6
7
Processing
Time
4
8
10
4
3
7
14
Due Date
-10
16
27
27
11
6
14
177
p.m.
p.m.
p.m
p.m
p.m
0
1-2/3
3-1/6
3-1/2
3
Production and Operations Analysis, Fourth Edition
1.
Find job scheduled 7th. Candidates are 4, 6, 7
= 50.
min[50-27, 50-6, 50-14] = min[23, 44, 36] = 23 at job
2.
Find job scheduled 6th. Candidates are 6, 7
= 50 - 4 = 46
min[46-6, 46-14] = 32 at job 7.
3.
Find job scheduled 5th. Candidates are 2, 3, 6
= 46 - 14 = 32
min[32-16, 32-27, 32-6] = 5 at job 3.
4.
Find job scheduled 4th. Candidates are 2, 5, 6
= 32 - 10 = 22
min[22-16, 22-11, 22-6] = 6 at job 2.
5.
Find job scheduled 3rd. Candidates are 5 and 6.
= 22 - 8 = 14.
min[14-11, 14-6] = 3 at job 5.
6.
Find job scheduled 2nd. Candidates are 1 and 6.
= 14 - 3 = 11.
min[11 - 10, 11-6] = 5 at job 6.
4.
Optimal Sequence:
8.12
1-6-5-2-3-7-4
(n!)m = (12!)6 = 1.2079 x 1052
50
The time required to evaluate all schedules is 1.2079 x 10
enormous number.
9
seconds which is an
There are 60 x 60 x 24 x 365 x 100 = 3.1536 x 10 seconds in a century. Hence, it
40
would require 3.8302 x 10
centuries to evaluate all schedules.
178
Solutions for Chapter 8
8.15
This is an example of 2 jobs on 5 machines where the sisters correspond to the jobs and
the advisors to machines.
120
History
Optimal
Solution
100
80
Science
English
60
C
40
Religion
20
A
Math
0
0
20
Math
40
60
History
80
English
100
120
Sci- Religion
ence
The optimal solution is indicated above. Suppose they begin at 12:00 noon. Then,
Marcia
Math:
Religion:
English:
Science:
History:
Mary
12:00-12:20
12:20-12:45
12:45-12:55
12:55- 1:30
1:30- 2:00
Math:
12:20-1:00
History:
1:00-1:15
English:
1:15-1:40
Science:
1:40-1:55
Religion: 1:55-2:15
Total elapsed time is 2 hours and 15 minutes.
179
Production and Operations Analysis, Fourth Edition
8.18
a)
Landing
time(E(ti)
Plane
1
2
3
4
5
Number of
Passengers(1/ui)
26
11
19
16
23
E(ti/ui)
180
12
45
75
252
4680
132
855
1200
5796
2-3-4-1-5
b)
Plane
1
2
3
4
5
E(ti)
26
26
19
16
23
Std. Deviation
()
26/3
11/3
19/3
16/3
23/3
95
Variance
676/9
121/9
361/9
256/9
529/9
1943/9
Since the landing times are independent and normally distributed, the total landing
is also normally distributed with mean
5
E(ti ) = 95
i =1
and variance
(var iances)
i=1
P{landing time 100}
= 1943/9 = (14.69)2
= P
landing time 95 100 95
14.69
14.69
= P{Z .3402} = .6338
The answer will not change if planes are landed in a different sequence because
landing times are independent. The sequencing does not affect the total landing
time.
180
Solutions for Chapter 8
8.23
= 30 per hour
= 60/1.2 = 50 per hour
= 30/50 = .60.
a) L = /(1 - ) = .60/.40 = 1.5
Lq = L = (.6)(1.5) = 0.9.
b) Wq = Lq/ = .9/30 = .03 hours = 1.8 minutes.
W = L/ = 1.5/30 = .05 hours = 3 minutes.
c) P0 = 1 - = .40
d) P0 + P1 = P0(1 + ) = (.4)(1.6) = .64.
e) P{W > 1/6} = e-(
8.25
- )t
= e-20/6 = .0357.
= 57 per hour
= 60 per hour
= 57/60 = 0.95
a) EFCFS(W) = 1/( - ) = 1/3 hours (= 20 minutes)
Using Figure 8.13, it follows that for = .95, the relative flow time is approximately
.35. It follows that
ESPT(W) = (.35)(1/3) = .1167 hours.
b) P{W > .5} = e
-( - )t
= e
-3/2
= .2231
c) To answer this part, we need to compute the variance of the flow time under LCFS.
EFCFS(W2) = 2[EFCFS(W)]2 = 2(1/3)2 = 2/9 hrs2.
ELCFS(W2)=(1/(1 - .95))(2/9)=4.44 hrs2, giving Var(W)= 4.33.
PLCFS{W > 1/2}P{ Z > (1/2 - 1/3)/ 4.33 }=P{Z >
.0801}=.4681.
181
Production and Operations Analysis, Fourth Edition
8.27
a)
Task
Positional Weight
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Ranking:
b)
100
94
46
43
37
47
23
20
29
16
16
20
12
8
5
1-2-6-3-4-5-9-7-8-12-10-11-13-14-15
100/30 = 3.333... implying a minimum of 4 stations would be required.
Stations
Tasks
Idle time
c)
1,2,6,3
2
4,5,7,9
1
8,12,10,11
2
10,13,14,15
15
Start with C = 25. A perfect balance would require four stations. Unfortunately
this is not possible.
For C = 2 6 we do find the following 4-station balance:
Stations
Tasks
Idle time
8.28
1
1,2,3,5
0
4,6,7,9
0
9,11,12
1
10,13,14,15
3
For a 3-station case, the smallest possible cycle time is 100/3 = 33.33 34.
C = 34
Stations
Tasks
Idle time
1
1,2,3,4,6
1
2
5,8,9,12
1
182
3
7,10,11,13,14,15
0
