Chapter 16 – Scheduling
16–41
12. Given:
A shoe repair operation uses a two-step procedure that all jobs in a certain category follow. The
jobs are shown below:
Time (minutes)
Job
WS A
WS B
A
27
45
B
18
33
C
70
30
D
26
24
E
15
10
a. Find the sequence that will minimize total completion 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 (10). Because the time is at Workstation B, schedule Job E
last (5th). Eliminate Job E from further consideration.
1st 2nd 3rd 4th 5th
Time (minutes)
Job
WS A
WS B
A
27
45
B
18
33
C
70
30
D
26
24
E
15
10
(b) Job B has the shortest time (18). Because the time is at Workstation A, schedule Job B
first (1st). Eliminate Job B from further consideration.
1st 2nd 3rd 4th 5th
B
Time (minutes)
Job
WS A
WS B
A
27
45
B
18
33
C
70
30
D
26
24
E
15
10
Chapter 16 – Scheduling
16–42
Education.
(c) Job D has the shortest time (24). Because the time is at Workstation B, schedule Job D
toward the end of the sequence (4th). Eliminate Job D from further consideration.
1st 2nd 3rd 4th 5th
B
D
Time (minutes)
Job
WS A
WS B
A
27
45
B
18
33
C
70
30
D
26
24
E
15
10
(d) Job A has the shortest time (27). Because the time is at Workstation A, schedule Job A
toward the beginning of the sequence (2nd). Eliminate Job A from further consideration.
1st 2nd 3rd 4th 5th
B
A
D
Time (minutes)
Job
WS A
WS B
A
27
45
B
18
33
C
70
30
D
26
24
E
15
10
(e) 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
B
A
C
D
Time (minutes)
Job
WS A
WS B
A
27
45
B
18
33
C
70
30
D
26
24
E
15
10
Chapter 16 – Scheduling
16–43
Education.
b. Determine the amount of idle time for Workstation B:
0 18 45 115 141 156
B
A
C
D
E
B
A
C
D
E
0 18 51 96 115 145 169 179
The idle time for Station B is = 18 + 19 = 37 minutes.
c. Determine the jobs that are candidates for splitting. Determine how much idle time and
makespan would be reduced by splitting those jobs.
The answers for these questions are somewhat subjective. Students may answer that all of the
Batch
Time (min.)
Workstation
A
Time (min.)
Workstation
B
B1
9 (18/2)
16.5 (33/2)
B2
9 (18/2)
16.5 (33/2)
A1
13.5 (27/2)
22.5 (45/2)
A2
13.5 (27/2)
22.5 (45/2)
C1
35 (70/2)
15 (30/2)
C2
35 (70/2)
15 (30/2)
D1
13 (26/2)
12 (24/2)
D2
13 (26/2)
12 (24/2)
E1
7.5 (15/2)
5 (10/2)
E2
7.5 (15/2)
5 (10/2)
Before we draw the chart, we can use a table to solve for the start and finish times for all
batches at Workstations A & B. After that, we can construct the chart.
Workstation A
Workstation B
Batch
Start
Finish
Start
Finish
B1
0
9
9
25.5
B2
9
18
25.5
42
A1
18
31.5
42
64.5
A2
31.5
45
64.5
87
C1
45
80
87
102
C2
80
115
115
130
D1
115
128
130
142
D2
128
141
142
154
E1
141
148.5
154
159
E2
148.5
156
159
164
141 156
0 9 18 31.5 45 80 115 128 148.5
B1
B2
A1
A2
C1
C2
D1
D2
E1
E2
B1 B2
A1 A2
C2
D1 D2
E1 E2
C1
Chapter 16 – Scheduling
Education.
(b) Jobs A, E, & C have the shortest times (2). Because the times for Jobs A & E are at Cutting,
break the tie arbitrarily by scheduling Job A toward the beginning of the sequence (2nd),
followed by Job E (3rd). (Note: Scheduling Job E 2nd and Job A 3rd would result in an
alternate optimal sequence with the same makespan and total idle time.) Eliminate Jobs A &
E from further consideration. Because the time for Job C is at Polishing, schedule Job C
toward the end of the sequence (6th). Eliminate Job C from further consideration.
1st 2nd 3rd 4th 5th 6th 7th
G
A
E
C
F
Job
Cutting
Polishing
A
2
3
B
4
3
C
5
2
D
4
5
E
2
3
F
3
1
G
1
4
(c) Job B has the shortest time (3). Because the time for Job B is at Polishing, schedule Job B
toward the end of the sequence (5th). Eliminate Job B from further consideration.
1st 2nd 3rd 4th 5th 6th 7th
G
A
E
B
C
F
Job
Cutting
Polishing
A
2
3
B
4
3
C
5
2
D
4
5
E
2
3
F
3
1
G
1
4
(d) Job D is the only job remaining. Schedule Job D 4th and eliminate Job D from further
consideration. The final schedule is shown below:
1st 2nd 3rd 4th 5th 6th 7th
G
A
E
D
B
C
F
Job
Cutting
Polishing
A
2
3
B
4
3
C
5
2
D
4
5
E
2
3
F
3
1
G
1
4
Chapter 16 – Scheduling
16–47
Education.
The start and finish times for the jobs at Cutting and Polishing are shown in the table below:
Cutting
Polishing
Job
Start
Finish
Start
Finish
G
0
1
1
5
A
1
3
5
8
E
3
5
8
11
D
5
9
11
16
B
9
13
16
19
C
13
18
19
21
F
18
21
21
22
Chapter 16 – Scheduling
16–48
Education.
14. Given:
Processing times for seven jobs are provided below. The seven jobs must follow the same
sequence through Grinding and Deburring.
Processing Time
(hours)
Job
Grinding
Deburring
A
3
6
B
2
4
C
1
5
D
4
3
E
9
4
F
8
7
G
6
2
a. Prepare a schedule using SPT for the Grinding department:
SPT Sequence: C-B-A-D-G-F-E
b. Determine flow time in the Grinding department and the total time needed to process the jobs
in both departments:
SPT
Grinding
Deburring
Job
Start
Finish
Start
Finish
C
0
1
1
6
B
1
3
6
10
A
3
6
10
16
D
6
10
16
19
G
10
16
19
21
F
16
24
24
31
E
24
33
33
37
93
The Grinding flow time is 93 hours. The total time (makespan) is 37 hours.
Chapter 16 – Scheduling
16–49
Education.
c. Determine a sequence that will minimize the total time needed to process the jobs in both
departments and the resulting flow time for the Grinding department:
Apply Johnson’s rule:
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.
Processing Time
(hours)
Job
Grinding
Deburring
A
3
6
B
2
4
C
1
5
D
4
3
E
9
4
F
8
7
G
6
2
(a) Job C has the shortest time (1). Because the time for Job C is at Grinding, schedule
Job C first (1st). Eliminate Job C from further consideration.
1st 2nd 3rd 4th 5th 6th 7th
C
Processing Time
(hours)
Job
Grinding
Deburring
A
3
6
B
2
4
C
1
5
D
4
3
E
9
4
F
8
7
G
6
2
16–50
Education.
(b) Jobs B & G have the shortest times (2). Because the time for Job B is at Grinding,
schedule Job B toward the beginning of the sequence (2nd). Eliminate Job B from
further consideration. Because the time for Job G is at Deburring, schedule Job G last
(7th). Eliminate Job G from further consideration.
1st 2nd 3rd 4th 5th 6th 7th
C
B
G
Processing Time
(hours)
Job
Grinding
Deburring
A
3
6
B
2
4
C
1
5
D
4
3
E
9
4
F
8
7
G
6
2
(c) Jobs A & D have the shortest times (3). Because the time for Job A is at Grinding,
schedule Job A toward the beginning of the sequence (3rd). Eliminate Job A from
further consideration. Because the time for Job D is at Deburring, schedule Job D
toward the end of the sequence (6th). Eliminate Job D from further consideration.
1st 2nd 3rd 4th 5th 6th 7th
C
B
A
D
G
Processing Time
(hours)
Job
Grinding
Deburring
A
3
6
B
2
4
C
1
5
D
4
3
E
9
4
F
8
7
G
6
2