Job Sequencing with Deadlines, in depth: the slack test, online admission with eviction, release windows, m machines and weighted lengths

The slack test

For unit jobs on one machine with slots 1, 2, 3 and so on, a set of jobs is feasible exactly when, for every time t, the number of jobs with deadline at most t is at most t. Call slack(t) = t - #{jobs with deadline <= t}; the set is feasible when slack is never negative.

Necessity is counting: jobs due by t must all occupy slots 1 to t. Sufficiency is earliest deadline first: run the jobs in deadline order; the i-th job occupies slot i, and since at least i jobs have deadline at most its deadline, the condition says i is at most that deadline. With m identical machines each time unit holds m jobs, so the condition becomes #{deadline <= t} <= m * t, and the same argument fills slots m at a time.

def feasible(jobs, m=1):
    """jobs: iterable of (deadline, profit); unit length, m machines."""
    deadlines = sorted(d for d, _ in jobs)
    return all(i + 1 <= m * d for i, d in enumerate(deadlines))

Because feasible sets are closed under removal and satisfy the exchange property, they form a matroid, and that is why the profit greedy is optimal for any profits. More useful in practice, the test gives an O(n log n) algorithm that scans in deadline order instead of profit order and works unchanged for m machines:

import heapq

def best_profit(jobs, m=1):
    kept = []                          # min-heap of profits currently kept
    for d, profit in sorted(jobs):     # deadline order
        heapq.heappush(kept, profit)
        if len(kept) > m * d:          # slack(d) went negative
            heapq.heappop(kept)        # drop the cheapest kept job
    return sum(kept)

Dropping the cheapest job is safe because every kept job has deadline at most d, so removing any one of them restores slack at d, and the cheapest removal loses the least. The heap version needs no slot array, so it also works when deadlines are huge timestamps rather than small integers.

Worked example: five jobs

Five jobs, one machine: a (deadline 2, profit 100), b (1, 19), c (2, 27), d (1, 25), e (3, 15). In deadline order the scan sees b, d, a, c, e.

The answer is 142 from a, c and e, the same as the profit-order greedy. The scan never needed to know where each job sits, only how many are due by each deadline.

From the kept set to a schedule

The deadline-order heap returns which jobs to run, not when. To get slots, store (profit, deadline, job_id) tuples in the heap instead of bare profits, then run earliest deadline first over the survivors. With m machines the i-th job in deadline order goes to time slot i // m + 1 on machine i % m:

def schedule(kept, m=1):
    """kept: feasible list of (deadline, job_id). Returns job_id -> (slot, machine)."""
    plan = {}
    for i, (deadline, job_id) in enumerate(sorted(kept)):
        slot = i // m + 1
        assert slot <= deadline, "kept set was not feasible"
        plan[job_id] = (slot, i % m)
    return plan

For the example the plan is a in slot 1, c in slot 2 and e in slot 3. The assertion is the slack test restated, so it doubles as a cheap runtime check that the selection step and the scheduling step agree on the slot convention. This schedule packs jobs as early as possible. The profit-order algorithm with latest-free-slot packs them as late as possible; both are valid, but early packing leaves the tail of the horizon free for late arrivals, while late packing leaves early slots free for urgent ones. Choose deliberately.

Online admission with eviction

Now let jobs arrive in arbitrary order, and after each arrival keep the most profitable feasible set. The matroid view says exactly what to do: adding one job to an optimal set creates at most one minimal infeasible subset, a circuit, and removing the cheapest member of that circuit gives the new optimum.

Slack identifies the circuit. Inserting a job with deadline d lowers slack on every t from d to the horizon T. If slack goes negative, let t1 be the first negative point. Removing any kept job with deadline at most t1 raises slack on [its deadline, T], which covers t1 and every later violation; removing a job due after t1 does not. So the circuit is the set of kept jobs (including the new one) with deadline at most t1, and we evict its cheapest member.

A segment tree over t with range add and a find-first-negative query does the slack bookkeeping in O(log T). Lazy segment trees covers the tree itself; the admission logic is short:

class OnlineJobSet:
    def __init__(self, horizon):
        self.T = horizon
        self.slack = SlackTree(horizon)   # slack[t] = t initially, range add, first < 0
        self.kept = []                    # (deadline, profit, id)

    def insert(self, deadline, profit, job_id):
        d = min(deadline, self.T)
        self.kept.append((d, profit, job_id))
        self.slack.add(d, self.T, -1)
        t1 = self.slack.first_negative()
        if t1 is None:
            return None                   # admitted, nothing evicted
        victim = min((j for j in self.kept if j[0] <= t1), key=lambda j: j[1])
        self.kept.remove(victim)
        self.slack.add(victim[0], self.T, +1)
        return victim                     # may be the job just inserted

As written the victim search is a linear scan, so an insert costs O(n + log T). To make it logarithmic, keep a min-heap of profits per deadline and a second segment tree holding each deadline's cheapest profit, and query the minimum over [1, t1]. Replaying the example in arrival order a, b, c, d, e evicts b when c arrives, rejects d immediately (it is the cheapest job due by 2), and ends at 142.

Release windows

Give each unit job a release time r as well as a deadline: it may run in any slot [t, t+1) with r <= t and t + 1 <= d. The counting test no longer suffices, but feasible sets are still a matroid: jobs are matched to slots in a bipartite graph, and matchable subsets form a transversal matroid. So the profit greedy is still optimal; it just needs a different oracle. For unit jobs with integer times, earliest deadline first among released jobs is an exact feasibility test:

def edf_feasible(jobs):
    """jobs: list of (release, deadline, profit), unit length, one machine."""
    jobs = sorted(jobs)
    ready, i, t = [], 0, 0
    while i < len(jobs) or ready:
        if not ready and jobs[i][0] > t:
            t = jobs[i][0]                      # idle until the next release
        while i < len(jobs) and jobs[i][0] <= t:
            heapq.heappush(ready, jobs[i][1]); i += 1
        if t + 1 > heapq.heappop(ready):       # earliest deadline missed
            return False
        t += 1
    return True

def best_with_windows(jobs):
    chosen = []
    for job in sorted(jobs, key=lambda j: -j[2]):   # richest first
        if edf_feasible(chosen + [job]):
            chosen.append(job)
    return sum(j[2] for j in chosen)

This is O(n^2 log n), fine for thousands of jobs. For larger inputs, run the greedy with an incremental bipartite matching instead of re-simulating.

Jobs with lengths and weights

When jobs have lengths p and weights w, maximising the weight of on-time jobs on one machine is weakly NP-hard; it contains 0/1 knapsack as the case where every deadline is equal. The unweighted case is solved greedily by Moore-Hodgson, covered in the base article. The weighted case has a pseudo-polynomial dynamic programme due to Lawler and Moore (1969): schedule on-time jobs in deadline order, and run a knapsack over total processing time with each job's capacity capped at its own deadline.

def max_on_time_weight(jobs):
    """jobs: (length, deadline, weight); returns the best on-time weight."""
    jobs = sorted(jobs, key=lambda j: j[1])        # earliest due date order
    horizon = max(d for _, d, _ in jobs)
    best = [float("-inf")] * (horizon + 1)
    best[0] = 0                                    # best[t]: on-time set ending at t
    for length, deadline, weight in jobs:
        for t in range(deadline, length - 1, -1):  # finish no later than deadline
            best[t] = max(best[t], best[t - length] + weight)
    return max(best)

It runs in O(n * D) time for the largest deadline D. When D is large, scale and round times, or switch to an integer programme. The connection to 0/1 knapsack is direct: the inner loop runs backwards for the same reason.

Testing against brute force

Every routine here is easy to get subtly wrong, usually at an off-by-one on deadlines or slots. The cure is a brute-force oracle over all subsets and a few hundred random small instances:

import itertools, random

def brute(jobs, m=1):
    return max(sum(p for _, p in s)
               for r in range(len(jobs) + 1)
               for s in itertools.combinations(jobs, r) if feasible(s, m))

for _ in range(400):
    jobs = [(random.randint(1, 4), random.randint(1, 20))
            for _ in range(random.randint(0, 7))]
    m = random.randint(1, 2)
    assert best_profit(jobs, m) == brute(jobs, m), (jobs, m)

Use the same pattern for the online structure (compare after every insert), the window greedy and the dynamic programme. Keep deadlines small so ties and full slots happen often; that is where the bugs live.

Where this shows up

• Batch GPU or render slots. Nightly jobs with value and a must-finish-by time, admitted as they are submitted; the online structure tells a submitter immediately whether their job displaced someone else's.
• Ad or promotion slots. Unit placements with expiry and bid, where new bids arrive continuously.
• Maintenance windows. Tasks with release and due times on a shared crew, the window variant.

Failure modes

• Mixing slot conventions. Whether deadline d means finishing by time d or starting in slot d changes every comparison. Fix one convention and test it.
• Deadlines beyond the horizon. Clamp them to the number of slots, or the slack tree indexes past its end.
• Eviction without notification. In online admission, an admitted job can later be evicted. If callers treat admission as final, either commit jobs once their slot is near or tell evicted owners.
• Using the DP with large timestamps. O(n * D) with D in seconds over a month is billions of cells.

Trade-offs

Profit-order with union-find slots is the fastest offline method and also gives each job its slot. The deadline-order heap is simpler, handles huge deadlines and m machines, but gives the set, not the slots; run EDF afterwards for the schedule. Online admission costs a tree but answers immediately. Release windows trade the counting test for a simulation or a matching. Non-unit weighted jobs leave the greedy world entirely.

What to do next

1. Write down your slot convention, then implement feasible and best_profit.
2. Add the brute-force harness and run it on a few hundred random small cases.
3. If jobs arrive over time, build the online structure and decide how evicted owners are told.
4. If jobs have release times, switch to the EDF oracle and re-run the harness with windows.
5. If lengths differ and weights matter, check that the largest deadline keeps the DP affordable.
6. Compare with next-free-slot union-find when you also need slot assignments.