Job Scheduling with Deadlines, in depth: the profit-maximising greedy, union-find slots, Moore-Hodgson, EDF and where greedy stops working

The problem, stated precisely

Input: n jobs, each with an integer deadline d (at least 1) and a profit p. Every job takes exactly one time unit, and the machine runs one job per unit, in slots 1, 2, 3 and so on. A job scheduled in slot t is on time if t is at most d. Goal: choose a set of jobs and assign them distinct slots so that every chosen job is on time and the total profit is as large as possible. Jobs not chosen are simply dropped; there is no penalty beyond the lost profit.

Two facts simplify everything. First, no useful schedule needs more than n slots, so any deadline larger than n can be capped at n. Second, a set of jobs is feasible, meaning it can be scheduled with nobody late, exactly when for every t, the number of chosen jobs with deadline at most t is at most t. Equivalently, sort the set by deadline and run it in that order; if anyone is late in that order, the set is infeasible in every order. That test is the whole reason the greedy works.

The greedy: richest job first, latest free slot

Sort jobs by profit, highest first. For each job, look for the latest free slot at or before its deadline. If there is one, put the job there; otherwise reject the job. Placing it as late as possible keeps early slots open for jobs with tighter deadlines that come later in the profit order.

Worked example with five jobs: A (deadline 2, profit 100), B (1, 19), C (2, 27), D (1, 25), E (3, 15). In profit order: A takes slot 2. C has deadline 2, slot 2 is taken, so it takes slot 1. D has deadline 1, slot 1 is taken, rejected. B, same, rejected. E has deadline 3 and takes slot 3. The schedule is C, A, E with profit 142. You can check by hand that no feasible set does better: A, B, C and D all have deadline 2 or less, so at most two of them fit, and the best two are A and C with 127; E is the only job that can use slot 3, adding 15.

Why it is optimal

The short argument is an exchange. Suppose an optimal set O differs from the greedy set G, and look at the most profitable job where they disagree. If it is in G but not O, add it to O and remove some job of O that is no more profitable and whose removal keeps O feasible; the profit does not drop, so O was not better. Such a job exists because of the counting condition above. If the first disagreement were a job in O but not G, the greedy would have accepted it, since every job G had already accepted is also in O and O is feasible. Repeat until O equals G.

The deeper reason is that feasible sets of unit jobs form a matroid: subsets of feasible sets are feasible, and any smaller feasible set can be extended by some job from a larger one. For any matroid with weights, sorting by weight and keeping each element that preserves independence is optimal. That is why profit order works here, and also why it stops working the moment durations differ: then the feasible sets are no longer a matroid.

Implementations: from quadratic to near-linear

The naive version scans backwards from each deadline looking for a free slot, which costs O(n) per job and O(n squared) overall. That is fine for a few thousand jobs and painful for a million. The fix is a disjoint-set structure over slots, where find(t) returns the latest free slot at or before t, and filling slot s merges it into slot s minus 1. Slot 0 is a sentinel meaning nothing is free. With path compression, each query is nearly constant, so the total cost is dominated by the sort.

def schedule_max_profit(jobs):
    """jobs: list of (name, deadline, profit); every job takes one time unit.
    Returns (total_profit, {slot: name}). O(n log n + n * alpha(n))."""
    n = len(jobs)
    horizon = min(n, max((d for _, d, _ in jobs), default=0))
    parent = list(range(horizon + 1))          # slot 0 is the "no slot left" sentinel

    def find(t):                                 # latest free slot <= t
        root = t
        while parent[root] != root:
            root = parent[root]
        while parent[t] != root:                 # path compression
            parent[t], t = root, parent[t]
        return root

    placed, total = {}, 0
    for name, d, profit in sorted(jobs, key=lambda j: (-j[2], j[1], j[0])):
        if d < 1 or profit <= 0:
            continue
        s = find(min(d, horizon))
        if s == 0:
            continue                             # no free slot at or before the deadline
        placed[s] = name
        total += profit
        parent[s] = s - 1                        # union with the slot to the left
    return total, dict(sorted(placed.items()))

jobs = [("A", 2, 100), ("B", 1, 19), ("C", 2, 27), ("D", 1, 25), ("E", 3, 15)]
print(schedule_max_profit(jobs))   # (142, {1: 'C', 2: 'A', 3: 'E'})

The disjoint-set details are covered in union-find, in depth. The iterative find is deliberate: a recursive one overflows Python's stack on long chains. The sort key breaks ties by deadline and then name, so equal-profit inputs always produce the same schedule, which matters for tests and for explaining decisions to users.

If you only need the best total profit or the set of jobs, not slot numbers, there is an even simpler sweep. Process jobs by increasing deadline, push each profit into a min-heap, and whenever the heap holds more jobs than the current deadline allows, pop the smallest. The heap always holds the best feasible set among the jobs seen so far.

import heapq

def max_profit_by_deadline(jobs):
    """Same answer, different sweep: scan by deadline, keep the best set in a min-heap."""
    kept = []                                    # min-heap of profits currently scheduled
    for _, d, profit in sorted(jobs, key=lambda j: j[1]):
        if profit <= 0:
            continue
        heapq.heappush(kept, profit)
        if len(kept) > d:                        # more unit jobs than slots up to d
            heapq.heappop(kept)                  # drop the least valuable
    return sum(kept)

On the example, the heap ends with 15, 27 and 100, again 142. Both versions run in O(n log n). The heap version is easier to get right and handles huge deadlines without allocating a slot array; the union-find version gives you the actual timetable. Heap operations are explained in heap operations.

When jobs have different lengths

Real jobs do not all take one unit. Once durations vary, the problem splits by objective, and each objective has its own answer.

• Minimise the maximum lateness (how late the worst job is). Sort by deadline and run in that order: earliest deadline first, also known as Jackson's rule. It is optimal by a swap argument: if two adjacent jobs are out of deadline order, swapping them never increases the maximum lateness.
• Minimise the number of late jobs, all jobs equal in value. The Moore-Hodgson algorithm: go through jobs in deadline order, add each to the schedule, and whenever the current job finishes late, remove the longest job scheduled so far. It runs in O(n log n) with a max-heap and is optimal.
• Maximise the total value of on-time jobs with arbitrary durations. This is weakly NP-hard, because it contains the knapsack problem: with a single common deadline it is knapsack. A dynamic program over jobs sorted by deadline, indexed by total processing time used, solves it in time proportional to n times the sum of durations, which is practical when durations are small integers. See dynamic programming for the technique.
• Minimise total weighted tardiness, where lateness costs in proportion to how late and how important. This is strongly NP-hard; real schedulers use dispatching rules, local search or integer programming, and accept approximate answers.

import heapq

def moore_hodgson(jobs):
    """jobs: list of (name, duration, deadline). Minimises the NUMBER of late jobs.
    Returns (on_time_in_order, late)."""
    on_time, heap, t = [], [], 0                 # heap holds (-duration, name)
    for name, p, d in sorted(jobs, key=lambda j: j[2]):   # earliest due date first
        on_time.append(name)
        heapq.heappush(heap, (-p, name))
        t += p
        if t > d:                                # deadline missed: drop the longest so far
            neg_p, drop = heapq.heappop(heap)
            on_time.remove(drop)
            t += neg_p
    late = [j[0] for j in jobs if j[0] not in on_time]
    return on_time, late

print(moore_hodgson([("J1", 2, 3), ("J2", 3, 5), ("J3", 1, 6), ("J4", 2, 7)]))
# (['J1', 'J3', 'J4'], ['J2'])

Worked through: in deadline order J1 finishes at 2 (deadline 3), J2 at 5 (deadline 5), J3 at 6 (deadline 6), and J4 at 8, past its deadline of 7. The longest scheduled job is J2 with duration 3, so it is dropped and the clock goes back to 5. Three jobs are on time and the remaining ones still run in deadline order: J1 from 0 to 2, J3 from 2 to 3, J4 from 3 to 5.

Where the profit greedy fails, with numbers

Apply the profit-first idea to jobs with durations and it breaks immediately. One machine, deadline 10 for all jobs. Job X takes 10 units and pays 11. Jobs Y and Z each take 5 units and pay 10. Profit order picks X first, which fills the whole window, for a total of 11. Running Y and Z instead pays 20. Sorting by profit per unit of time fixes this example but not the general case, because the problem contains knapsack, where no ratio rule is optimal.

The lesson is to classify before coding. Unit durations and total profit: greedy by profit. Arbitrary durations and maximum lateness: earliest deadline first. Arbitrary durations and number of late jobs: Moore-Hodgson. Arbitrary durations and weighted on-time value: dynamic programming or a solver. If you cannot place your problem in one of these rows, assume it is hard until proven otherwise.

Using it in real systems

Production scheduling adds things the textbook leaves out. Time must be discretised: decide whether a slot is a minute, a batch window or a GPU hour, and convert deadlines with a consistent rounding rule, because a deadline rounded up admits a job that will actually be late. Jobs arrive over time, so a nightly batch planner reruns the algorithm at each planning point over the jobs that are known, and it must not reshuffle work that is already running. Several machines change the problem again: identical parallel machines with unit jobs still have a greedy solution, but with arbitrary durations even minimising the makespan is NP-hard.

Profits are usually estimates, not facts. If two jobs differ in value by less than your estimation error, the choice between them is noise, and a stable tie-break such as earlier submission is more defensible to users than an arbitrary flip. Log the rejected jobs and the reason, latest free slot unavailable, so that a team whose job was dropped can see what displaced it.

Failure modes in code

What to do next

1. Write down your objective and whether durations are equal; use the classification table to pick the algorithm.
2. For unit jobs and total profit, implement the heap sweep first and the union-find version only if you need slot assignments.
3. Add a feasibility checker (sort by deadline, simulate) and run it on every output in tests.
4. Write a brute-force solver for up to ten jobs and compare it with your implementation on random inputs.
5. Make tie-breaking explicit and deterministic, and round deadlines down when converting to slots.
6. Log rejected jobs with the reason, and review rejected high-value jobs as a signal that capacity is short.