Job Sequencing with Deadlines

The problem

There is one machine and n jobs. Every job takes exactly one unit of time, has a deadline d and a profit p. A job earns its profit only if it finishes by its deadline, i.e. if it runs in one of the time slots 1, 2, …, d. Which jobs should be done, and in which order, to earn the most?

Example (the default in the 3D model):

The greedy algorithm

sort the jobs by profit, highest first
for each job, with deadline d:
    find the latest free slot t with t ≤ d
    if there is one: put the job in slot t
    else: reject the job

The schedule is J3, J1, J5 with total profit 100 + 27 + 15 = 142. J4 is more profitable than J5, but it must be done in slot 1, and slot 1 is better used for J3.

The second example (7 jobs with profits 35, 30, 25, 20, 15, 12, 5 and deadlines 3, 4, 4, 2, 3, 1, 2) gives the schedule J4, J3, J1, J2 with profit 110; J5, J6 and J7 are rejected.

Why the latest free slot?

A job can run in any slot up to its deadline. Choosing the latest possible one leaves the early slots, which are the only ones jobs with short deadlines can use, as free as possible. If J1 (deadline 2) had taken slot 1, J3 (deadline 2) would still fit in slot 2, but in other cases an early slot taken too soon blocks a job that had nowhere else to go.

Why is greedy optimal?

A set of jobs can be scheduled exactly when, for every t, at most t of them have a deadline ≤ t. Suppose some optimal schedule differs from the greedy one, and look at the most profitable job where they differ:

• If greedy took job j and the optimal schedule did not, adding j to the optimal set and removing a cheaper job (one must exist, or the optimum could simply add j) keeps it feasible and does not lower the profit.
• Repeating this exchange turns the optimal schedule into the greedy one without losing profit.

(In the language of the theory, the feasible job sets form a matroid, and on a matroid the greedy algorithm “heaviest element first” is always optimal.) The code below also checks greedy against brute force on 2000 random examples.

Making it fast

Sorting costs O(n log n). Scanning back from each deadline can cost up to D steps per job, so the simple version is O(n · D), which is O(n²) when deadlines are large.

A union–find structure removes the scan. Let each slot t point to the latest free slot at or before t. Finding a slot is a find; after filling slot t, union it with slot t − 1. With path compression this is almost constant time per job, so the whole algorithm is dominated by the sort: O(n log n).

Related problems

Code

from itertools import combinations

def job_sequencing(jobs):
    """jobs: (name, profit, deadline); each job takes 1 time unit. Greedy: most profitable first,
    placed in the LATEST free slot on or before its deadline."""
    slots = [None] * (max(d for _, _, d in jobs) + 1)      # slots[1..D]; slot t = time t-1 to t
    log = []
    for name, profit, deadline in sorted(jobs, key=lambda j: -j[1]):
        for t in range(deadline, 0, -1):
            if slots[t] is None:
                slots[t] = name
                log.append(f'{name} -> slot {t}')
                break
        else:
            log.append(f'{name} rejected')
    chosen = [s for s in slots[1:] if s]
    profit = sum(p for n, p, _ in jobs if n in chosen)
    return chosen, profit, log

def best_by_brute_force(jobs):
    """Try every subset; a subset is feasible if, sorted by deadline, the i-th job has deadline >= i."""
    best = 0
    for k in range(len(jobs) + 1):
        for sub in combinations(jobs, k):
            if all(d >= i for i, (_, _, d) in enumerate(sorted(sub, key=lambda j: j[2]), 1)):
                best = max(best, sum(p for _, p, _ in sub))
    return best

EX1 = [('J1', 100, 2), ('J2', 19, 1), ('J3', 27, 2), ('J4', 25, 1), ('J5', 15, 3)]
EX2 = [('J1', 35, 3), ('J2', 30, 4), ('J3', 25, 4), ('J4', 20, 2), ('J5', 15, 3), ('J6', 12, 1), ('J7', 5, 2)]
for jobs in (EX1, EX2):
    chosen, profit, log = job_sequencing(jobs)
    print(chosen, profit, 'brute force:', best_by_brute_force(jobs))
    print('   ', log)
# ['J3', 'J1', 'J5'] 142 brute force: 142
#     ['J1 -> slot 2', 'J3 -> slot 1', 'J4 rejected', 'J2 rejected', 'J5 -> slot 3']
# ['J4', 'J3', 'J1', 'J2'] 110 brute force: 110
#     ['J1 -> slot 3', 'J2 -> slot 4', 'J3 -> slot 2', 'J4 -> slot 1', 'J5 rejected', 'J6 rejected', 'J7 rejected']

import random
rng = random.Random(1)
for _ in range(2000):                                      # greedy is always optimal
    jobs = [(f'J{i}', rng.randint(1, 50), rng.randint(1, 5)) for i in range(rng.randint(1, 8))]
    assert job_sequencing(jobs)[1] == best_by_brute_force(jobs)
print('greedy = brute force on 2000 random job sets')
# greedy = brute force on 2000 random job sets

Common mistakes

• Sorting by deadline instead of profit. That answers a different question (how many jobs fit), not which earn the most.
• Putting a job in the earliest free slot. It can block a later job that has a short deadline.
• Placing a job after its deadline. Only slots 1 … d are allowed for a job with deadline d.
• Forgetting that every job takes exactly one unit. With different durations the greedy method is no longer correct.
• Reporting the jobs in profit order. The final schedule runs them in slot order (J3, J1, J5), not in the order they were chosen.