Three Slots, Five Orders: Two Scheduling Heuristics on Trial
Glilot Fresh runs one refrigerated van on a single morning route, 08:00–11:00, split into three one-hour slots numbered 1, 2 and 3. Each accepted order occupies exactly one slot and must be delivered no later than its deadline slot; an order that cannot make its deadline is not delivered at all and earns nothing. Tomorrow's confirmed orders are: A (deadline 1, ₪90), B (deadline 3, ₪300), C (deadline 3, ₪300), D (deadline 3, ₪120) and E (deadline 2, ₪150). The driver suggests: "At every slot, take the waiting order whose deadline is earliest." The owner suggests: "Sort the orders by profit, highest first, and drop each one into the latest slot still free before its deadline." A developer proposes replacing both rules with dynamic programming, but is uneasy: next quarter the order table will hold 40,000 rows, deadlines will be stored in minutes rather than hours, and some orders will require two consecutive slots because the northern customers are grouped into one long run.
1. Apply the driver's earliest-deadline rule to tomorrow's five orders. Give the resulting schedule, its total profit and the best achievable total, and explain what the gap tells you about earliest-deadline-first.
Read the worked answer
Running EDF. Slot 1 takes the ready order with the smallest deadline: A (d=1). Slot 2 takes E (d=2). Slot 3: B, C and D all have d=3, so any of them can be chosen - take B. Schedule A→1, E→2, B→3, profit 90+150+300 = ₪540; C and D are rejected and earn nothing.
Optimum. Reject A. Put E in slot 1 (deadline 2 is still met), B in slot 2, C in slot 3: 150+300+300 = ₪750. D cannot improve this (120 < 300), and four orders cannot fit into three slots.
What the gap means. EDF optimises the number of on-time jobs when all jobs have equal value; it is blind to weights. Here it spends a scarce slot on the cheapest order on the board, and the loss is 210 shekels - 28% of the optimum. This is structural, not a tie-breaking accident: any instance with a tight-deadline low-profit job and a loose-deadline high-profit job breaks EDF, and the gap widens as the deadline spread grows. The correct statement in an exam answer is precise: EDF is optimal for 1|p_j=1|ΣU_j (count of late jobs), not for the weighted objective the depot actually cares about.
2. Apply the owner's rule and justify why it is optimal here. Then show that the detail "latest still-free slot" matters by re-running the rule with "earliest free slot".
Read the worked answer
Running the owner's rule. Sorted by profit: B(300), C(300), E(150), D(120), A(90). B goes to the latest free slot ≤ 3 → slot 3. C → slot 2. E (d=2) → the latest free slot ≤ 2 is slot 1. D (d=3) finds no free slot ≤ 3 → rejected. A (d=1) → rejected. Total ₪750, which matches the optimum found by hand.
Why it cannot be beaten (exchange argument). Claim: after processing the k most profitable orders, greedy's schedule is a subset of some optimal schedule. Let j be order k+1 and S an optimal schedule containing greedy's first k placements. If j ∈ S, move j (if needed) to greedy's slot: that slot is free in S and ≤ d_j, so it stays feasible. If j ∉ S and some slot s ≤ d_j is free in S, insert j at greedy's slot and profits rise - contradicting optimality, unless S is already full at or before d_j. In that case the only order j can displace sits exactly in greedy's slot s, and that order was processed after j, so its profit is ≤ profit(j); swapping keeps feasibility (s ≤ d_j) and does not lower profit. Hence j can always be added without loss.
Placing j as late as possible is what makes the swap work: it guarantees the slots after s, up to d_j, are already occupied, so the only displacement candidate is at s. Re-run with "earliest free slot": B→1, C→2, E has no slot ≤ 2 left → rejected, D→3, total 300+300+120 = ₪720. Same rule, same data, 30 shekels worse. The choice of slot is part of the algorithm, not an implementation detail.
3. The route grows to four slots and some orders need two consecutive slots. Does the owner's rule survive? Give a counterexample on three slots, and advise the developer on an exact method that still works with 40,000 rows and deadlines in minutes.
Read the worked answer
No - it collapses. Three slots, four orders: P needs two consecutive slots, deadline 3, profit ₪50; Q, R and S each need one slot, deadline 3, profit ₪40. Profit-descending puts P first → slots 2–3, then Q → slot 1, and R, S are rejected: 50+40 = ₪90. The optimum drops P and runs Q, R, S in slots 1, 2, 3: ₪120. A multi-slot job consumes capacity several cheap jobs would have shared, and profit ordering cannot see that trade. In general, maximising profit with processing times and deadlines on one machine (1||Σw_jU_j) is NP-hard, so no sort-and-place rule will be correct.
Exact method that fits the real data. The horizon is tiny even though n is not: 40,000 rows but D = 180 minutes. Sort orders by deadline and compute dp[i][t] = best profit using a subset of the first i orders that occupies exactly t slots; a state is legal only while t ≤ d_i, because for any fixed feasible set the earliest-deadline order is feasible (Jackson's rule), so "total slots used" is a sufficient state. Answer = max over t of dp[n][t]. Time O(n·D) ≈ 7.2 million steps; memory O(D) with a rolling array. Reject orders longer than the horizon up front and convert minutes to a common slot unit before indexing - otherwise the deadline comparison silently mixes units.
Caveat for the developer. If the horizon ever stretches to weeks, D explodes and the DP becomes pseudo-polynomial in practice; then switch to an ILP solver or a documented heuristic, and say so in the design note rather than pretending the DP scales.