Question 16.2: Determining Job Sequences Using Various Rules Processing tim...
Determining Job Sequences Using Various Rules
Processing times (including setup times) and due dates for six jobs waiting to be processed at a work center are given in the following table. Determine the sequence of jobs, the average flow time, average tardiness, and average number of jobs at the work center, for each of these rules:
a. FCFS
b. SPT
c. EDD
d. CR
| Job | Processing Time (days) |
Due Date (days from present time) |
| A | 2 | 7 |
| B | 8 | 16 |
| C | 4 | 4 |
| D | 10 | 17 |
| E | 5 | 15 |
| F | 12 | 18 |
Assume jobs arrived in the order shown.
a. The FCFS sequence is simply A-B-C-D-E-F. The measures of effectiveness are as follows (see table):
(1) Average flow time: 120/6 = 20 days.
(2) Average tardiness: 54/6 = 9 days.
(3) The makespan is 41 days. Average number of jobs at the work center: 120/41 = 2.93.
| Job Sequence |
(1) Processing Time |
(2) Flow Time |
(3) Due Date |
(2) – (3) Days Tardy [0 if negative] |
| A | 2 | 2 | 7 | 0 |
| B | 8 | 10 | 16 | 0 |
| C | 4 | 14 | 4 | 10 |
| D | 10 | 24 | 17 | 7 |
| E | 5 | 29 | 15 | 14 |
| F | \frac{12}{41} | \frac{41}{120} | 18 | \frac{23}{54} |
The flow time column indicates cumulative processing time, so summing these times and dividing by the total number of jobs processed indicates the average time each job spends at the work center. Similarly, find the average number of jobs at the center by summing the flow times and dividing by the total processing time.
The Excel solution is shown in Table 16.5.
b. Using the SPT rule, the job sequence is A-C-E-B-D-F (see the following table). The resulting values for the three measures of effectiveness are:
(1) Average flow time: 108/6 = 18 days.
(2) Average tardiness: 40/6 = 6.67 days.
(3) Average number of jobs at the work center: 108/41 = 2.63.
| Job Sequence |
(1) Processing Time |
(2) Flow Time |
(3) Due Date |
(2) – (3) Days Tardy [0 if negative] |
| A | 2 | 2 | 7 | 0 |
| C | 4 | 6 | 4 | 2 |
| E | 5 | 11 | 15 | 0 |
| B | 8 | 19 | 16 | 3 |
| D | 10 | 29 | 17 | 12 |
| F | \frac{12}{41} | \frac{41}{108} | 18 | \frac{23}{40} |
c. Using earliest due date as the selection criterion, the job sequence is C-A-E-B-D-F.
The measures of effectiveness are as follows (see table):
(1) Average flow time: 110/6 = 18.33 days.
(2) Average tardiness: 38/6 = 6.33 days.
(3) Average number of jobs at the work center: 110/41 = 2.68.
| Job Sequence |
(1) Processing Time |
(2) Flow Time |
(3) Due Date |
(2) – (3) Days Tardy [0 if negative] |
| C | 4 | 4 | 4 | 0 |
| A | 2 | 6 | 7 | 0 |
| E | 5 | 11 | 15 | 0 |
| B | 8 | 19 | 16 | 3 |
| D | 10 | 29 | 17 | 12 |
| F | \frac{12}{41} | \frac{41}{110} | 18 | \frac{23}{38} |
d. Using the critical ratio we find:
| Job Sequence |
Processing Time |
Due Date |
Critical Ratio Calculation |
| A | 2 | 7 | (7 − 0)/2 = 3.5 |
| B | 8 | 16 | (16 − 0)/8 = 2.0 |
| C | 4 | 4 | (4 − 0)/4 = 1.0 (lowest) |
| D | 10 | 17 | (17 − 0)/10 = 1.7 |
| E | 5 | 15 | (15 − 0)/5 = 3.0 |
| F | 12 | 18 | (18 − 0)/12 = 1.5 |
At day 4 [C completed], the critical ratios are
| Job Sequence |
Processing Time |
Due Date |
Critical Ratio Calculation |
| A | 2 | 7 | (7 − 4)/2 = 1.5 |
| B | 8 | 16 | (16 − 4)/8 = 1.5 |
| C | — | — | — |
| D | 10 | 17 | (17 − 4)/10 = 1.3 |
| E | 5 | 15 | (15 − 4)/5 = 2.2 |
| F | 12 | 18 | (18 − 4)/12 = 1.17 (lowest) |
At day 16 [C and F completed], the critical ratios are
| Job Sequence |
Processing Time |
Due Date |
Critical Ratio Calculation |
| A | 2 | 7 | (7 − 16)/2 = −4.5 (lowest) |
| B | 8 | 16 | (16 − 18)/8 = 0.0 |
| C | — | — | — |
| D | 10 | 17 | (17 − 16)/10 = 0.1 |
| E | 5 | 15 | (15 − 16)/5 = −0.2 |
| F | — | — | — |
At day 18 [C, F, and A completed], the critical ratios are:
| Job Sequence |
Processing Time |
Due Date |
Critical Ratio Calculation |
| A | — | — | — |
| B | 8 | 16 | (16 − 18)/8 = −0.25 |
| C | — | — | — |
| D | 10 | 17 | (17 − 18)/10 = −0.10 |
| E | 5 | 15 | (15 − 18)/5 = −0.60 (lowest) |
| F | — | — | — |
At day 23 [C, F, A, and E completed], the critical ratios are
| Job Sequence |
Processing Time |
Due Date |
Critical Ratio Calculation |
| A | — | — | — |
| B | 8 | 16 | (16 − 23)/8 = −0.875 (lowest) |
| C | — | — | — |
| D | 10 | 17 | (17 − 23)/10 = −0.60 |
| E | — | — | — |
| F | — | — | — |
The job sequence is C-F-A-E-B-D, and the resulting values for the measures of effectiveness are as follows:
(1) Average flow time: 133/6 = 22.17 days.
(2) Average tardiness: 58/6 = 9.67 days.
(3) Average number of jobs at the work center: 133/41 = 3.24.
| Sequence | (1) Processing Time |
(2) Flow Time |
(3) Due Date |
(2) – (3) Days Tardy |
| C | 4 | 4 | 4 | 0 |
| F | 12 | 16 | 18 | 0 |
| A | 2 | 18 | 7 | 11 |
| E | 5 | 23 | 15 | 8 |
| B | 8 | 31 | 16 | 15 |
| D | \frac{10}{41} | \frac{41}{133} | 17 | \frac{24}{58} |
The results of these four rules are summarized in Table 16.6.
TABLE 16.6 Comparison of the four rules for Example 2
| Rule | Average Flow Time (days) |
Average Tardiness (days) |
Average Number of Jobs at the Work Center |
| FCFS | 20.00 | 9.00 | 2.93 |
| SPT | 18.00 | 6.67 | 2.63 |
| EDD | 18.33 | 6.33 | 2.68 |
| CR | 22.17 | 9.67 | 3.24 |
