Chapter 16 – Scheduling
16–31
Education.
(b) Order B has the shortest time (0.90). Because the time is at Step 1, schedule Order B first
(1st) . Eliminate Order B from further consideration.
1st 2nd 3rd 4th 5th 6th 7th
B
C
Time (hours)
Order
Step 2
A
1.40
B
1.30
C
0.80
D
1.50
E
1.80
F
1.75
G
1.40
(c) Order A has the shortest time (1.20). Because the time is at Step 1, schedule Order A
B
A
C
Time (hours)
Order
Step 2
A
1.40
B
1.30
C
0.80
D
1.50
E
1.80
F
1.75
G
1.40
1st 2nd 3rd 4th 5th 6th 7th
B
A
G
C
Time (hours)
Order
Step 2
A
1.40
B
1.30
C
0.80
D
1.50
E
1.80
F
1.75
G
1.40
Chapter 16 – Scheduling
16–32
(e) Order D has the shortest time (1.50). Because the time is at Step 2, schedule Order D
toward the end of the sequence (6th). Eliminate Order D from further consideration.
1st 2nd 3rd 4th 5th 6th 7th
B
A
G
D
C
Time (hours)
Order
Step 2
A
1.40
B
1.30
C
0.80
D
1.50
E
1.80
F
1.75
G
1.40
1st 2nd 3rd 4th 5th 6th 7th
B
A
G
E
D
C
Time (hours)
Order
Step 2
A
1.20
1.40
B
1.30
C
0.80
D
1.50
E
1.80
F
1.75
G
1.40
(g) Order F is the only order remaining. Schedule Order F 5th. Eliminate Order F from further
consideration. The final schedule is shown below:
1st 2nd 3rd 4th 5th 6th 7th
B
A
G
E
F
D
C
Time (hours)
Order
Step 2
A
1.40
B
1.30
C
0.80
D
1.50
E
1.80
F
1.75
G
1.40
16–33
Education.
10. Given:
The times required to complete each of 8 jobs in a two-machine flow shop are shown in the table
below. Each job must follow the same sequence, beginning with Machine A and moving to
Machine B.
Time (hours)
Job
Machine
B
a
5
b
13
c
6
d
7
e
14
f
4
g
14
h
20
11
a. Determine a sequence that will minimize makespan time:
We will use Johnson’s rule to sequence the jobs. The Johnson’s rule steps from the text are
shown below:
1. Select the job with the shortest time. If the shortest time is at the first work center,
2. Eliminate the job and its time from further consideration.
3. Repeat steps 1 and 2, working toward the center of the sequence, until all jobs have been
scheduled.
(a) Job e has the shortest time (2). Because the time is at Machine A, schedule Job e first
(1st). Eliminate Job e from further consideration.
1st 2nd 3rd 4th 5th 6th 7th 8th
e
Time (hours)
Job
Machine
B
a
5
b
13
c
6
d
7
e
14
f
4
g
14
h
11
Chapter 16 – Scheduling
16–34
Education.
(b) Job b has the shortest time (3). Because the time is at Machine A, schedule Job b toward
the beginning of the sequence (2nd). Eliminate Job b from further consideration.
1st 2nd 3rd 4th 5th 6th 7th 8th
e
b
Time (hours)
Job
Machine
B
a
5
b
13
c
6
d
7
e
14
f
12
4
g
18
14
h
11
(c) Job f has the shortest time (4). Because the time is at Machine B, schedule Job f last (8th).
Eliminate Job f from further consideration.
1st 2nd 3rd 4th 5th 6th 7th 8th
e
b
f
Time (hours)
Job
Machine
B
a
5
b
13
c
6
d
7
e
14
f
4
g
18
14
h
11
Chapter 16 – Scheduling
(d) Job a has the shortest time (5). Because the time is at Machine B, schedule Job a toward
the end of the sequence (7th). Eliminate Job a from further consideration.
1st 2nd 3rd 4th 5th 6th 7th 8th
e
b
a
f
Time (hours)
Job
Machine
B
a
5
b
13
c
6
d
7
e
14
f
12
4
g
18
14
h
20
11
(e) Job c has the shortest time (6). Because the time is at Machine B, schedule Job c toward
the end of the sequence (6th). Eliminate Job c from further consideration.
1st 2nd 3rd 4th 5th 6th 7th 8th
e
b
c
a
f
Time (hours)
Job
Machine
B
a
5
b
13
c
6
d
7
e
14
f
4
g
14
h
11
Chapter 16 – Scheduling
Education.
(f) Job d has the shortest time (7). Because the time is at Machine B, schedule Job d toward
the end of the sequence (5th). Eliminate Job d from further consideration.
1st 2nd 3rd 4th 5th 6th 7th 8th
e
b
d
c
a
f
Time (hours)
Job
Machine
B
a
5
b
13
c
6
d
7
e
14
f
12
4
g
18
14
h
20
11
(g) Job h has the shortest time (11). Because the time is at Machine B, schedule Job h toward
the end of the sequence (4th). Eliminate Job h from further consideration.
1st 2nd 3rd 4th 5th 6th 7th 8th
e
b
h
d
c
a
f
Time (hours)
Job
Machine
B
a
5
b
13
c
6
d
7
e
14
f
4
g
14
h
11
Chapter 16 – Scheduling
(h) Job g is the only job remaining. Schedule Job g 3rd. Eliminate Job g from further
consideration. The final schedule is shown below:
1st 2nd 3rd 4th 5th 6th 7th 8th
e
b
g
h
d
c
a
f
Time (hours)
Job
Machine
B
a
5
b
13
c
6
d
7
e
14
f
12
4
g
18
14
h
20
11
b. Construct a chart of the resulting sequence, and Machine B’s idle time:
0 2 5 23 43 51 60 76 88
e
b
g
h
d
c
a
f
e
b
g
h
d
c
a
f
0 2 16 29 43 54 61 67 76 81 88 92
c. Determine how much Machine B’s idle time would be reduced by splitting the last two jobs
in half:
Original idle time for Machine B: 2 + 9 + 7 = 18 hours, and the original makespan = 92
4/2 = 2
Chapter 16 – Scheduling
16–38
After splitting, we obtain the following Gantt chart:
0 2 5 23 43 51 60 68 76 82 88
e
b
g
h
d
c
a1
a2
f1
f2
e
b
g
h
d
c
a1
a2
f1
f2
0 2 16 29 43 54 61 67 68 70.5 76 78.5 84 90
11. Given:
Given the operation times provided:
Time (minutes)
Job
Center 1
Center 2
A
20
27
B
16
30
C
43
51
D
60
12
E
35
28
F
42
24
a. Develop a job sequence that minimizes idle time at the two work centers.
We will use Johnson’s rule to sequence the jobs. The Johnson’s rule steps from the text are
shown below:
1. Select the job with the shortest time. If the shortest time is at the first work center,
schedule that job first; if the time is at the second work center, schedule the job last.
Break ties arbitrarily.
scheduled.
(a) Job D has the shortest time (12). Because the time is at Center 2, schedule Job D last
(6th). Eliminate Job D from further consideration.
1st 2nd 3rd 4th 5th 6th
D
Time (minutes)
Job
Center 1
Center 2
A
20
27
B
16
30
C
43
51
D
60
12
E
35
28
F
42
24
Chapter 16 – Scheduling
16–39
(b) Job B has the shortest time (16). Because the time is at Center 1, schedule Job B first
(1st). Eliminate Job B from further consideration.
1st 2nd 3rd 4th 5th 6th
B
D
Time (minutes)
Job
Center 1
Center 2
A
20
27
B
16
30
C
43
51
D
60
12
E
35
28
F
42
24
(c) Job A has the shortest time (20). Because the time is at Center 1, schedule Job A toward
the beginning of the sequence (2nd). Eliminate Job A from further consideration.
1st 2nd 3rd 4th 5th 6th
B
A
D
Time (minutes)
Job
Center 1
Center 2
A
20
27
B
16
30
C
43
51
D
60
12
E
35
28
F
42
24
(d) Job F has the shortest time (24). Because the time is at Center 2, schedule Job F toward
the end of the sequence (5th). Eliminate Job F from further consideration.
1st 2nd 3rd 4th 5th 6th
B
A
F
D
Time (minutes)
Job
Center 1
Center 2
A
20
27
B
16
30
C
43
51
D
60
12
E
35
28
F
42
24
16–40
Education.
1st 2nd 3rd 4th 5th 6th
B
A
E
F
D
Time (minutes)
Job
Center 1
Center 2
A
20
27
B
16
30
C
43
51
D
60
12
E
35
28
F
42
24
(f) Job C is the only job remaining. Schedule Job C 3rd. Eliminate Job C from further
consideration. The final schedule is shown below:
1st 2nd 3rd 4th 5th 6th
B
A
C
E
F
D
Time (minutes)
Job
Center 1
Center 2
A
20
27
B
16
30
C
43
51
D
60
12
E
35
28
F
42
24
b. Construct a chart of the activities at the two centers, and determine each one’s idle time:
0 16 36 79 114 156 216
B
A
C
E
F
D
B
A
C
E
F
D
0 16 46 73 79 130 158 182 216 228
Center 1: 0 minutes of idle time.
Center 2: 16 + 6 + 34 = 56 minutes of idle time.