Question 2 of 6: Priority Dispatching at a Work Centre

Question 2: Priority Dispatching at a Work Centre (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Six job orders queued at a single work centre, with the due dates, arrival times, operation times and downstream operation counts of Table 2 of the paper.

Find. The priority value of every order under each of the five dispatch rules, the processing sequence each rule produces, and a reasoned choice of the rule to run the centre on.

Approach. Each rule is a scalar priority computed from the table alone, so the work is to evaluate the five priority expressions, sort each one, and then discriminate between the resulting sequences on the two measures a single work centre can actually influence — mean flow time and tardiness against the due dates.

1. Part (a) — FCFS: rank by arrival time at the centre. The priority is the clock time in the third column, earliest first, and no arithmetic is needed. Order 1 arrived Apr. 18 at 9 a.m., order 3 on Apr. 19 at 5 p.m., order 5 on Apr. 20 at 5 p.m., and the remaining three all on Apr. 21 at 10 a.m., 3 p.m. and 5 p.m. respectively: $$\text{FCFS:}\quad \boxed{1 \rightarrow 3 \rightarrow 5 \rightarrow 2 \rightarrow 4 \rightarrow 6}$$ Note that this rule uses only the arrival column: it is blind to how long a job takes and to when it is wanted.
2. Part (b) — SOT: rank by operation time, shortest first. Reading the fourth column and sorting ascending gives 3 h for order 2, then 4, 6, 7, 8 and 9 h: $$\text{SOT:}\quad \boxed{2 \rightarrow 5 \rightarrow 1 \rightarrow 3 \rightarrow 6 \rightarrow 4}$$ The total work content is unchanged at $\sum t_i = 6+3+7+9+4+8 = 37\ \text{h}$; only the order in which it is discharged has changed.
3. Part (c) — SS: static slack is the due date less the arrival date at the centre. Working in whole days, and remembering that April has 30 days, $$\mathrm{SS}_i = d_i - a_i$$ with $d_i$ the due date and $a_i$ the date the order reached the centre. For order 1, May 1 less Apr. 18 is 13 days; for order 3, June 1 less Apr. 19 is $11 + 31 + 1 = 43$ days; for order 4, June 15 less Apr. 21 is $9 + 31 + 15 = 55$ days. Order 2 is the interesting case: it is due Apr. 20 but only reached the centre on Apr. 21, so its slack is negative and it is already late on arrival.
4. Sort the slacks, smallest first. The six values are $-1$, 13, 43, 55, 25 and 29 days for orders 1 to 6 respectively, so $$\text{SS:}\quad \boxed{2 \rightarrow 1 \rightarrow 5 \rightarrow 6 \rightarrow 3 \rightarrow 4}$$ Unlike FCFS and SOT this rule looks forward to the promise made to the customer, but it still ignores how much work each job carries.
5. Part (d) — FISFS: a due-date system, first in system first served. Under a due-date system the order that entered the system first is the one that was promised first, so its due date is the earliest; sequencing by earliest due date and sequencing by order of entry are the same instruction. Sorting the second column gives Apr. 20, May 1, May 15, May 20, June 1, June 15: $$\text{FISFS:}\quad \boxed{2 \rightarrow 1 \rightarrow 5 \rightarrow 6 \rightarrow 3 \rightarrow 4}$$ This is identical to the static-slack sequence. That is not a coincidence to be glossed over: the six arrivals are spread over only four days while the due dates span two months, so subtracting the arrival date barely re-orders anything. Static slack and earliest due date diverge only when arrival times are dispersed on the same scale as the due dates.
6. Part (e) — SS/RO: slack per remaining operation. Dividing each static slack by the number of operations the job still has to pass through, $$\frac{\mathrm{SS}_i}{\mathrm{RO}_i}:\quad \frac{13}{3} = 4.33,\quad \frac{-1}{1} = -1.00,\quad \frac{43}{2} = 21.50,\quad \frac{55}{4} = 13.75,\quad \frac{25}{5} = 5.00,\quad \frac{29}{7} = 4.14$$ in days per operation for orders 1 to 6. Sorting ascending, $$\text{SS/RO:}\quad \boxed{2 \rightarrow 6 \rightarrow 1 \rightarrow 5 \rightarrow 4 \rightarrow 3}$$ The rule promotes order 6, which has a comfortable 29 days of slack but seven operations still to go, and demotes order 3, which has 43 days of slack and only two operations left. It is the only rule of the five that recognises the job's remaining routing.
7. Score the sequences on mean flow time. With the centre starting on the queue at time zero, the completion time of the job in position $k$ is the cumulative operation time, and the mean flow time is $$\bar{F} = \frac{1}{n}\sum_{k=1}^{n} \sum_{j=1}^{k} t_{[j]}$$ For SOT the completion times are 3, 7, 13, 20, 28 and 37 h, so $\bar{F} = 108/6 = 18.00\ \text{h}$; for FCFS they are 6, 13, 17, 20, 29 and 37 h, giving $\bar{F} = 122/6 = 20.33\ \text{h}$. Repeating for the other two distinct sequences, $$\boxed{\bar{F}_{\mathrm{SOT}} = 18.00\ \text{h} < \bar{F}_{\mathrm{SS}} = 18.50\ \text{h} < \bar{F}_{\mathrm{SS/RO}} = 19.83\ \text{h} < \bar{F}_{\mathrm{FCFS}} = 20.33\ \text{h}}$$ This ordering is not an accident of the data: SOT provably minimises mean flow time on a single machine, and because mean flow time, mean lateness and average work-in-process at the centre are all proportional to the same sum, SOT simultaneously minimises all three.
8. Score the sequences on delivery performance. Taking time zero as Apr. 21 at 5 p.m., when the last order joins the queue, and converting the due dates at eight working hours per day, the allowances are $-8$, 80, 328, 440, 192 and 232 h for orders 2, 1, 3, 4, 5 and 6. Every completion time is at most 37 h, so the only order that can possibly finish late is order 2, which was late before it arrived. Its tardiness is 20 h of processing plus the 8 h it was already overdue under FCFS, against 3 h plus 8 h under the other three rules, so the mean tardiness across the six jobs is 4.67 h for FCFS and 1.83 h for SOT, SS/FISFS and SS/RO alike, with exactly one tardy job in every case.
9. Choose a rule. On this queue SOT is the best of the five: it gives the lowest mean flow time, ties for the lowest tardiness, and needs only the operation-time column, which is the one datum a work centre always has. Its known weakness is that long jobs are pushed to the back of the queue every time a short job arrives, so on a live centre with continuous arrivals a job can starve indefinitely. The standard remedy is to truncate the rule — run SOT but promote any job whose waiting time exceeds a threshold, or fall back to earliest due date once a job's slack goes negative. If the centre is one station of a multi-stage shop rather than the last one, SS/RO is the better choice despite its slightly worse mean flow time here, because it is the only rule that allocates the remaining slack across the operations still to be performed and so protects the schedule downstream.