Chapter 16 – Scheduling
16–21
Education.
Job D is scheduled third.
At day 21 + 6 = 27 [Job D completed], only Job B remains.
Job B is scheduled fourth and will be completed on day 27 + 10 = 37.
b. For each of the methods above, determine the (1) average flow time, (2) average tardiness,
Makespan = Total of job times.
FCFS:
Job time
Flow time
Due date
Days
Job
(days)
(days)
(days)
tardy
A
14
14
20
0
B
10
24
16
8
C
7
31
15
16
D
6
37
17
20
37
106
44
Average job flow time = Total job flow time / Number of jobs = 106 / 4 = 26.50 days.
Average job tardiness = Total job tardiness / Number of jobs = 44 / 4 = 11.00 days.
Average number of jobs = Total flow time / Makespan = 106 / 37 = 2.86 jobs.
A
14
37
20
17
37
79
24
Average number of jobs = Total flow time / Makespan = 79 / 37 = 2.14 jobs.
SPT:
Job time
Flow time
Due date
Days
Job
(days)
(days)
(days)
tardy
D
6
6
17
0
C
7
13
15
0
B
10
23
16
7
Chapter 16 – Scheduling
16–22
Education.
Average job flow time = Total job flow time / Number of jobs = 84 / 4 = 21.00 days.
B
10
37
16
21
37
99
37
Average number of jobs = Total flow time / Makespan = 99 / 37 = 2.68 jobs.
c. SPT is superior because it provides the lowest value for each of the three measures.
EDD:
Job time
Flow time
Due date
Days
Job
(days)
(days)
(days)
tardy
C
7
7
15
0
B
10
17
16
1
D
6
23
17
6
A
14
37
20
17
37
84
24
CR:
Job time
Flow time
Due date
Days
Job
(days)
(days)
(days)
tardy
A
14
14
20
0
C
7
21
15
6
D
6
27
17
10
a
4
c
12
d
11
20
e
15
7. Given:
The following table contains information on five jobs waiting for processing at a work center (the
jobs are listed in the order of their arrival):
Job
Processing
Time per
Unit
(hours)
Units per
Job
Setup
Time
(hours)
Due Date
(hours)
a
.14
45
0.7
4
b
.25
14
0.5
10
c
.10
18
0.2
12
d
.25
40
1.0
20
e
.10
75
0.5
15
We need total processing time for each job: (Processing time per unit * Units per job) + Setup
time:
Job a: (.14 * 45) + 0.7 = 7 hours
Chapter 16 – Scheduling
16–24
Education.
SPT Sequence: c-b-a-e-d
SPT:
Job time
Flow time
Due date
Hours
Job
(hours)
(hours)
(hours)
tardy
c
2
2
12
0
b
4
6
10
0
a
7
13
4
9
e
8
21
15
6
d
11
32
20
12
32
74
27
Average job flow time = Total job flow time / Number of jobs = 74 / 5 = 14.80 hours.
Average job tardiness = Total job tardiness / Number of jobs = 27 / 5 = 5.40 hours.
Average number of jobs = Total flow time / Makespan = 74 / 32 = 2.31 jobs.
EDD Sequence: a-b-c-e-d
EDD:
Job time
Flow time
Due date
Hours
Job
(hours)
(hours)
(hours)
tardy
a
7
7
4
3
b
4
11
10
1
c
2
13
12
1
e
8
21
15
6
d
11
32
20
12
32
84
23
Average job flow time = Total job flow time / Number of jobs = 84 / 5 = 16.80 hours.
Average job tardiness = Total job tardiness / Number of jobs = 23 / 5 = 4.60 hours.
Average number of jobs = Total flow time / Makespan = 84 / 32 = 2.63 jobs.
Critical Ratio:
CR Calculations (round to 2 decimals):
Initial critical ratios at hour 0:
Job
Processing
Time
(hours)
Due Date
(hours)
Critical Ratio Calculation
a
7
4
(4 – 0) / 7 = 0.57 (lowest)
b
4
10
(10 – 0) / 4 = 2.50
c
2
12
(12 – 0) / 2 = 6.00
d
11
20
(20 – 0) / 11 = 1.82
e
8
15
(15 – 0) / 8 = 1.88
Job a is scheduled first.
Chapter 16 – Scheduling
16–25
Education.
At hour 0 + 7 = 7 [Job a completed], the critical ratios are:
Job
Processing
Time
(hours)
Due Date
(hours)
Critical Ratio Calculation
a
–
–
–
b
4
10
(10 – 7) / 4 = 0.75 (lowest)
c
2
12
(12 – 7) / 2 = 2.50
d
11
20
(20 – 7) / 11 = 1.18
e
8
15
(15 – 7) / 8 = 1.00
Job b is scheduled second.
At hour 7 + 4 = 11 [Job b completed], the critical ratios are:
Job
Processing
Time
(hours)
Due Date
(hours)
Critical Ratio Calculation
a
–
–
–
b
–
–
–
c
2
12
(12 – 11) / 2 = 0.50 (tied)
d
11
20
(20 – 11) / 11 = 0.82
e
8
15
(15 – 11) / 8 = 0.50 (tied)
At hour 11 + 2 = 13 [Job c completed], the critical ratios are:
Job
Processing
Time
(hours)
Due Date
(hours)
Critical Ratio Calculation
a
–
–
–
b
–
–
–
c
–
–
–
d
11
20
(20 – 13) / 11 = 0.64
e
8
15
(15 – 13) / 8 = 0.25 (lowest)
Job d is scheduled fifth and will be completed at hour 21 + 11 = 32.
Chapter 16 – Scheduling
16–26
CR Sequence: a-b-c-e-d
CR:
Job time
Flow time
Due date
Hours
Job
(hours)
(hours)
(hours)
tardy
a
7
7
4
3
b
4
11
10
1
c
2
13
12
1
e
8
21
15
6
d
11
32
20
12
32
84
23
Critical Ratio:
CR Calculations (round to 2 decimals):
Initial critical ratios at hour 0:
Job
Processing
Time
(hours)
Due Date
(hours)
Critical Ratio Calculation
a
7
4
(4 – 0) / 7 = 0.57 (lowest)
b
4
10
(10 – 0) / 4 = 2.50
c
2
12
(12 – 0) / 2 = 6.00
d
11
20
(20 – 0) / 11 = 1.82
e
8
15
(15 – 0) / 8 = 1.88
At hour 0 + 7 = 7 [Job a completed], the critical ratios are:
Job
Processing
Time
(hours)
Due Date
(hours)
Critical Ratio Calculation
a
–
–
–
b
4
10
(10 – 7) / 4 = 0.75 (lowest)
c
2
12
(12 – 7) / 2 = 2.50
d
11
20
(20 – 7) / 11 = 1.18
e
8
15
(15 – 7) / 8 = 1.00
Chapter 16 – Scheduling
At hour 7 + 4 = 11 [Job b completed], the critical ratios are:
Job
Processing
Time
(hours)
Due Date
(hours)
Critical Ratio Calculation
a
–
–
–
b
–
–
–
c
2
12
(12 – 11) / 2 = 0.50 (tied)
d
11
20
(20 – 11) / 11 = 0.82
e
8
15
(15 – 11) / 8 = 0.50 (tied)
Job
Processing
Time
(hours)
Due Date
(hours)
Critical Ratio Calculation
a
–
–
–
b
–
–
–
c
2
12
(12 – 19) / 2 = –3.50
d
11
20
(20 – 19) / 11 = 0.09
e
–
–
–
CR Sequence: a-b-e-c-d
CR:
Job time
Flow time
Due date
Hours
Job
(hours)
(hours)
(hours)
tardy
a
7
7
4
3
b
4
11
10
1
e
8
19
15
4
c
2
21
12
9
d
11
32
20
12
32
90
29
Average job flow time = Total job flow time / Number of jobs = 90 / 5 = 18.00 hours.
Average job tardiness = Total job tardiness / Number of jobs = 29 / 5 = 5.80 hours.
16–29
Education.
FCFS:
Job time
Flow time
Job
(days)
(days)
A
8
8
B
10
18
C
5
23
D
11
34
E
9
43
43
126
S/O Sequence: B-D-C-A-E
S/O:
Job time
Flow time
Job
(days)
(days)
B
10
10
D
11
21
C
5
26
A
8
34
E
9
43
43
134
Average number of jobs = Total flow time / Makespan = 134 / 43 = 3.12 jobs.
Alternate S/O Sequence: D-B-C-A-E
S/O:
Job time
Flow time
Job
(days)
(days)
D
11
11
B
10
21
C
5
26
A
8
34
E
9
43
43
135
Average job flow time = Total job flow time / Number of jobs = 135 / 5 = 27.00 days.
Average number of jobs = Total flow time / Makespan = 135 / 43 = 3.14 jobs.
16–30
Education.
9. Given:
A wholesale grocery distribution system uses a two-step process to fill orders. Tomorrow’s work
will consist of filling the seven orders shown below.
Time (hours)
Order
Step 1
Step 2
A
1.20
1.40
B
0.90
1.30
C
2.00
0.80
D
1.70
1.50
E
1.60
1.80
F
2.20
1.75
G
1.30
1.40
Determine a job sequence that will minimize the time required to fill the orders:
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
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) Order C has the shortest time (0.80). Because the time is at Step 2, schedule Order C last
(7th). Eliminate Order C from further consideration.
1st 2nd 3rd 4th 5th 6th 7th
C
Time (hours)
Order
Step 1
Step 2
A
1.20
1.40
B
0.90
1.30
C
2.00
0.80
D
1.70
1.50
E
1.60
1.80
F
2.20
1.75
G
1.30
1.40