J-1
Supplement
J
Operations Scheduling
DISCUSSION QUESTION
1. The optimizing approach, of course, would give the optimal schedule for a group of
jobs. However, implementing the model would be difficult. For example, significant
amounts of data would need to be maintained and updated each time the model was
used. There would also likely be circumstances when the schedule would have to be
manually adjusted to account for unexpected happenings. Of course, the model’s
PROBLEMS
Job Shop Scheduling
1. Hickory Company
a.
FCFS:
SPT:
EDD:
Job
Finish
Time
Flow
Time
Job
Hr Since
Order
Arrived
Finish
Time
Flow
Time
Job
Hr Since
Order
Arrived
Finish
Time
Flow
Time
1
10
22
2
10
3
13
2
10
3
13
2
13
23
5
1
10
11
1
12
13
25
3
28
35
4
3
19
22
3
7
28
35
4
37
40
1
12
29
41
4
3
37
40
5
44
45
3
7
44
51
5
1
44
45
Total
165
138
158
–
⚫
Supplement J
⚫
Operations Scheduling
J-2
b.
FCFS:
SPT:
EDD:
Average flow times
33.0
27.6
31.6
Average early time
0.4
3.4
1.0
Average past due
11.0
8.6
10.2
2. Drill press
a., b. The following tables give the solutions to parts (a) and (b) using the Single-
Workstation Scheduler from OM Explorer.
Note: OM Explorer prints out not just the Average Flow Times, but also the
Average Early Time and Average Past Due. These last two performance measures
are not shown here, because they are inappropriate. The reason is that times to due
date were expressed in terms of weeks, whereas the times since the jobs arrived
and the processing times of the jobs are expressed in terms of hours. The same
unit of time is needed for correct statistics on the last two performance measures.
c. Priority planning with an MRP system relies on proper timing of materials.
Operations Scheduling
⚫
Supplement J
⚫
J-3
3. Bycraft Enterprises
This problem has more complicated calculations, because (1) start times and finish
times are done by clock time, and (2) some of the jobs arrive after the first one is
started.
Job
Total Processing Time (hours)
1
50(.06) + 4 = 7.0
2
120(.05) + 3 = 9.0
3
260(.03) + 5 = 12.8
4
200(.04) + 2 = 10.0
a. Using SPT
Job
Arrival
Start
Finish
Flow (hr)
Past Due (hr)
1
9:00 A.M.(M)
9:00 A.M.(M)
4:00 P.M.(M)
7.0
0.0
2
10:00 A.M.(M)
4:00 P.M.(M)
1:00 A.M.(T)
15.0
3.0
4
12:00 P.M. (M)
1:00 A.M.(T)
11:00 A.M.(T)
23.0
9.0
3
11:00 A.M.(M)
11:00 A.M.(T)
11:48 P.M.(T)
36.8
24.8
Total
81.80
36.8
Monday
Tuesday
8–12
12–4
4–8
8–12
12–4
4–8
8–12
12–4
4–8
8–12
Job 1
Job 2
Job 4
Job 3
(7 hours)
(9 hours)
(10 hours)
(12.8 hours)
Using EDD
Job
Arrival
Start
Finish
Flow
Past Due
(hr)
(hr)
1
9:00 A.M.(M)
9:00 A.M.(M)
4:00 P.M.(M)
7.0
0.0
2
10:00 A.M.(M)
4:00 P.M.(M)
1:00 A.M.(T)
15.0
3.0
3
11:00 A.M.(M)
1:00 A.M.(T)
1:48 P.M.(T)
26.8
14.8
4
12:00 P.M.(M)
1:48 P.M.(T)
11:48 P.M.(T)
35.8
21.8
Total
84.6
39.6
Monday
Tuesday
8–12
12–4
4–8
8–12
12–4
4–8
8–12
12–4
4–8
8–12
Job 1
Job 2
Job 3
Job 4
(7 hours)
(9 hours)
(12.8 hours)
(10 hours)
⚫
Supplement J
⚫
Operations Scheduling
J-4
b.
SPT
EDD
Average flow time (hours)
20.45
21.15
Average hours past due
9.20
9.90
EDD minimizes the maximum number of past-due hours and the variance of the
past-due hours, but does worse with regard to average flow times and average
4. Standard Components
Processing
Shop Time
Slack per
Time
Due Date
Remaining
Operations
Slack
Remaining
Critical
Job
(days)
(days)
(days)
Remaining
(days)
Operation
Ratio
1
1.25
6
2.5
5
3.5
0.700
2.40
2
2.75
5
3.5
7
1.5
0.214
1.43
3
2.50
7
4.0
9
3.0
0.333
1.75
4
3.00
6
4.5
12
1.5
0.125
1.33
5
2.50
5
3.0
8
2.0
0.250
1.67
6
1.75
8
2.5
6
5.5
0.917
3.20
7
2.25
7
3.0
9
4.0
0.444
2.33
8
2.00
5
2.5
3
2.5
0.833
2.00
Rule
Sequence
FCFS
1
2
3
4
5
6
7
8
Due date
6
5
7
6
5
8
7
5
Completion
1.25
4.00
6.50
9.50
12.00
13.75
16.00
18.00
Days past due
0
0
0
3.50
7.00
5.75
9.00
13.00
SPT
1
6
8
7
3
5
2
4
Due date
6
8
5
7
7
5
5
6
Completion
1.25
3.00
5.00
7.25
9.75
12.25
15.00
18.00
Days past due
0
0
0
0.25
2.75
7.25
10.00
12.00
EDD
2
5
8
1
4
3
7
6
Due date
5
5
5
6
6
7
7
8
Completion
2.75
5.25
7.25
8.50
11.50
14.00
16.25
18.00
Days past due
0
0.25
2.25
2.50
5.50
7.00
9.25
10.00
S/RO
4
2
5
3
7
1
8
6
Due date
6
5
5
7
7
6
5
8
Completion
3.00
5.75
8.25
10.75
13.00
14.25
16.25
18.00
Days past due
0
0.75
3.25
3.75
6.00
8.25
11.25
10.00
CR
4
2
5
3
8
7
1
6
Due date
6
5
5
7
5
7
6
8
Completion
3.00
5.75
8.25
10.75
12.75
15.00
16.25
18.00
Days past due
0
0.75
3.25
3.75
7.75
8.00
10.25
10.00
Operations Scheduling
⚫
Supplement J
⚫
J-5
a. Relative performance. The following table shows that FCFS and SPT result in the
lowest proportion of past jobs completed. SPT results in the lowest average past
due, whereas EDD results in the lowest level of maximum past due.
Rule
% of Jobs
Past Due
Average Past
Due (days)
Maximum Past
Due (days)
FCFS
62.5%
4.781
13.00
SPT
62.5%
4.031
12.00
EDD
87.5%
4.594
10.00
S/RO
87.5%
5.406
11.25
CR
87.5%
5.469
10.25
b. All of these rules result in some jobs being past due. If customers can tolerate a
small amount of past due but would be very upset and likely to move their
business elsewhere if jobs are extremely past due, then SPT would be a good rule
to use.
5. Eight jobs processed on three machines
Job
1
2
3
4
5
6
7
8
Machine 1
2
5
2
3
1
2
4
2
Machine 2
4
1
3
5
5
6
2
1
Machine 3
6
4
5
2
3
2
6
2
a. Using SPT for M2, the makespan for the eight jobs is 38 hours.
Sequence 2–8–7–3–1–4–5–6
M1
6 1 7 8 Idle
2
M2
3 7 8 2
Idle 1 M3
2 am 4 5 6
3 7
2 8
Idle 1 4 5 6
7 am
3 4
5
b. We can use Johnson’s rule with some modifications. For example, we sum the
processing times of M1 and M2 and then sum the processing times of M2 and M3
as follows:
Job
M1 + M2
M2 + M3
1
6
10
2
6
5
3
5
8
4
8
7
5
6
8
6
8
8
7
6
8
8
3
3
⚫
Supplement J
⚫
Operations Scheduling
J-6
The result is a makespan of 35 hours. Note that Johnson’s rule utilizes M2 better
than when SPT was used for scheduling.
M1
0 3 6 9 12 15 18 21 24 27 30 33
2 7 3 Idle
8
M2
36 39
5 1 3 8
Idle 7 M3
2 A.M. 7 A.M.
6 4 2
5
8
7 6 4
6 4
2
1
5
3 1 Idle
Idle
6. Two operations scheduled through three machines
a. Job schedules using four rules:
i. SPT:
M1 Schedule
M2 Schedule
Start
Finish
Start
Finish
Job
Time
Time
Job
Time
Time
2
0
2
8
0
2
6
2
5
7
2
6
3
5
9
9
6
12
4
9
14
10
12
20
1
14
20
5
20
27
M3 Schedule
Arrival
Process
Job
Start
Finish
Hours
Past
Job
Time at
M3
Time
Sequence
Time
Time
Early
Due
2
2
1
2
2
3
15
—
8
2
10
8
3
13
18
—
6
5
1
6
13
14
15
—
7
6
6
4
14
17
—
1
3
9
7
7
17
23
19
—
9
12
9
10
23
25
15
—
4
14
3
1
25
29
—
16
10
20
2
5
29
33
—
3
1
20
4
3
33
40
—
18
5
27
4
9
40
49
—
1
Total
82
39
Average
8.2
3.9
Operations Scheduling
⚫
Supplement J
⚫
J-7
ii. EDD:
M1 Schedule
M2 Schedule
Start
Finish
Start
Finish
Job
Time
Time
Job
Time
Time
1
0
6
8
0
2
4
6
11
10
2
10
2
11
13
7
10
14
3
13
17
9
14
20
6
17
20
5
20
27
M3 Schedule
Arrival
Due
Job
Start
Finish
Hours
Past
Job
Time at
M3
Date
Sequence
Time
Time
Early
Due
8
2
31
8
2
12
19
—
1
6
13
1
12
16
—
3
10
10
40
4
16
19
—
3
4
11
16
2
19
20
—
2
2
13
18
3
20
27
—
5
7
14
42
6
27
28
1
—
3
17
22
5
28
32
—
2
6
20
29
10
32
34
6
—
9
20
48
7
34
40
2
—
5
27
30
9
40
49
—
1
Total
28
16
Average
2.8
1.6
⚫
Supplement J
⚫
Operations Scheduling
J-8
iii. S/RO:*
M1 Schedule
Start
Finish
Job
S/RO
Job
Time
Time
1
1.5
1
0
6
2
7.5
4
6
11
3
5.5
3
11
15
4
4.0
2
15
17
5
9.5
5
17
24
6
12.5
6
24
27
M2 Schedule
Start
Finish
Job
S/RO
Job
Time
Time
7
16.0
8
0
2
8
9.5
10
2
10
9
16.5
7
10
14
10
15.0
9
14
20
M3 Schedule
Arrival
Job
Start
Finish
Hours
Past
Job
Time at
M3
S/RO
Sequence
Time
Time
Early
Due
8
2
19
8
2
12
19
—
1
6
–3
1
12
16
—
3
10
10
0
4
16
19
—
3
4
11
–3
3
19
26
—
4
7
14
4
2
26
27
—
9
3
15
–4
5
27
31
—
1
2
17
–9
6
31
32
—
3
9
20
–1
7
32
38
4
—
5
24
–1
10
38
40
—
—
6
27
–3
9
40
49
—
1
Total
23
24
Average
2.3
2.4
Operations Scheduling
⚫
Supplement J
⚫
J-9
iv. CR:*
M1 Schedule
Start
Finish
Job
CR
Job
Time
Time
1
1.3
1
0
6
2
6.0
3
6
10
3
2.0
4
10
15
4
2.0
5
15
22
5
2.7
2
22
24
6
7.3
6
24
27
M2 Schedule
Start
Finish
Job
CR
Job
Time
Time
7
4.2
8
0
2
8
2.6
9
2
8
9
3.2
10
8
16
10
4.0
7
16
20
M3 Schedule
Arrival
Job
Start
Finish
Hours
Past
Job
Time at
M3
CR
Sequence
Time
Time
Early
Due
8
2
2.90
8
2
12
19
—
1
6
0.25
1
12
16
—
3
9
8
0.89
4
16
19
—
3
3
10
0.43
3
19
26
—
4
4
15
0.00
2
26
27
—
9
10
16
1.00
5
27
31
—
1
7
20
1.67
6
31
32
—
3
5
22
0.75
7
32
38
4
—
2
24
–8.00
10
38
40
—
—
6
27
–2.00
9
40
49
—
1
Total
23
24
Average
2.3
2.4
* Note: The S/RO and CR ratios at M3 are calculated each time the machine is available to
process another job. Only the jobs in queue at that instant are evaluated. The values in the
S/RO and CR columns are the values at the time the jobs were selected for processing.
b. EDD minimizes the past due but results in producing product early. If the product
⚫
Supplement J
⚫
Operations Scheduling
J-10
Flow Shop Scheduling
7. Refer to Gantt chart in Fig. J.4.
A
Job 1
Job 2
Job 3
Idle
B
Idle
Job 1
Job 2
Job 3
Machine
0
1
2
3
4
5
6
7
8
9
a. To minimize the makespan if each job must be processed on machine A
first, we can use Johnson’s rule:
Process Time (hr)
Job
Machine A
Machine B
1
2
1
2
1
4
3
3
2
The optimal sequence would be 2–3–1. The revised Gantt chart is:
A
Job 1
Job 2
Job 3
Idle
B
Idle
Job 1
Job 2
Job 3
Machine
0
1
2
3
4
5
6
7
8
9
The makespan is now 8 hours, which is an improvement of 1 hour.
b. Now suppose that the only restriction is that no job may be processed on
both machines at the same time. One of several schedules that yield a
makespan of 7 hours is given following:
A
Job 1
Job 2
Job 3
B
Job 1
Job 2
Job 3
Machine
Idle
Operations Scheduling
⚫
Supplement J
⚫
J-11
8. Manufacturer of small-boat sails
Job
1
2
3
4
5
6
7
8
9
10
Operation 1
1
5
8
3
9
4
7
2
4
9
Operation 2
8
3
1
2
8
6
7
2
4
1
a. One possible sequence is
1–8–6–7–5–9–2–4–10–3
b.
Machine 1
Machine 2
Job
Start
Finish
Start
Finish
1
0
1
1
9
8
1
3
9
11
6
3
7
11
17
7
7
14
17
24
5
14
23
24
32
9
23
27
32
36
2
27
32
36
39
4
32
35
39
41
10
35
44
44
45
3
44
52
52
53
The Gantt chart is shown following.
Oper 1
0 5 10 15 20 25 30 35 40 45 50 55
1
8 6 7 5 9 4 2 10 3
3
Oper 2 Idle
4 2 9 5 7 6 8
10
1
These calculations are confirmed by the following output from POM for Windows:
9. McGee Parts Company
⚫
Supplement J
⚫
Operations Scheduling
J-12
a. To minimize the makespan if each job must be deburred prior to heat treatment, we
can use Johnson’s rule:
Processing Time Days
Job
Debur
Heat Treat
1
2
6
2
3
5
3
7
4
4
3
8
5
1
5
6
8
2
One optimal sequence would be 5–1–2–4–3–6.
b. The Gantt chart is shown following. The orders can be shipped in 31 working
days.
Debur
5
1
2
4
3
6
Heat
Treat-
ment
5
1
2
4
3
6
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0
2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
32
10. Reliable Manufacturing
Job
1
2
3
4
5
6
7
8
Department 12
2
4
7
5
4
10
8
2
Department 22
3
6
3
8
2
6
6
5
a. SPT.
Department 12 Department 22
Process
Begin
End
Flow
Process
Begin
End
Flow
Job
Time
Time
Time
Time
Time
Time
Time
Time
1
2
0
2
2
3
2
5
5
8
2
2
4
4
5
5
10
10
5
4
4
8
8
2
10
12
12
2
4
8
12
12
6
12
18
18
4
5
12
17
17
8
18
26
26
3
7
17
24
24
3
26
29
29
7
8
24
32
32
6
32
38
38
6
10
32
42
42
6
42
48
48
141
186
i. Average flow time in Department 12 = (141/8) = 17.625 days
Operations Scheduling
⚫
Supplement J
⚫
J-13
b. Johnson’s rule minimizes makespan time when scheduling two facilities. First
we establish the sequence of jobs based on Johnson’s rule:
Department # 12
1
8
2
4
6
7
3
5
Department # 22
1
8
2
4
6
7
3
5
Department #1
Department #22
Process
Begin
End
Flow
Process
Begin
End
Flow
Job
Time
Time
Time
Time
Time
Time
Time
Time
1
2
0
2
2
3
2
5
5
8
2
2
4
4
5
5
10
10
2
4
4
8
8
6
10
16
16
4
5
8
13
13
8
16
24
24
6
10
13
23
23
6
24
30
30
7
8
23
31
31
6
31
37
37
3
7
31
38
38
3
38
41
41
5
4
38
42
42
2
41
43
43
161
206
i. Average flow time for Department 12 = (161/8) = 20.125 days.
c. The SPT rule results in a lower inventory of uncompleted jobs (see sum of job-
days). Johnson’s rule minimizes makespan for a set of jobs over a group of
machines. However, to implement Johnson’s rule, the informational requirements
⚫
Supplement J
⚫
Operations Scheduling
J-14
11. Penultimate Support Systems
Model
A
B
C
D
Fabrication
12
24
6
18
Assembly
8
30
12
15
Using Johnson’s rule, the sequence of Models is C–B–D–A.
Fabrication
0
10
20
30
40
50
60
70
80
C
B
D
A
Idle
Assembly
A
D
B
Idle
C
Fabrication
Assembly
Job
Start
Finish
Start
Finish
C
0
6
6
18
B
6
30
30
60
D
30
48
60
75
A
48
60
75
83