Unit-Time Job Sequencing with Deadlines

Each job takes one time slot, has an integer deadline $d_j$, and earns nonnegative profit $p_j$ only if completed by that deadline. Choose and schedule jobs to maximize total profit on one machine.

These unit-time and deadline assumptions are part of the problem; arbitrary durations require a different scheduling model.

Greedy rule

Process jobs by descending profit. Put each job into the latest still-empty slot no later than its deadline. Scheduling late preserves earlier slots for jobs with tighter deadlines.

sort jobs by decreasing profit
for each job:
    scan backward from min(deadline, number_of_jobs)
    place it in the first empty slot found

Why the choice works

The feasible sets of unit jobs satisfy an exchange structure: when a profitable job is accepted, moving it to its latest feasible slot leaves maximum room for the remaining jobs. A schedule can be exchanged into this form without reducing profit.

Cost and improvements

• Sorting costs $O(n\log n)$.
• A direct backward slot scan can cost $O(nD)$, bounded by $O(n^2)$ after capping useful deadlines at $n$.
• A disjoint-set structure can locate the latest available slot efficiently, making sorting the dominant term in common implementations.

Zero or negative-profit jobs should not be scheduled merely to fill space when jobs are optional.

The exchange step in detail

Assume all jobs are available at time zero, deadlines are integer completion times, and slot t occupies [t-1,t). There are no release times or precedence constraints. Compare the greedy partial schedule with an optimal schedule that already agrees with earlier greedy placements. For the next job j, let t be its latest free eligible slot. If the optimal schedule places j earlier, move it to t, swapping any occupant back to j's earlier slot; that occupant still meets its deadline. If j is absent, replace the occupant at t (or fill the empty slot). Any occupant there not previously fixed cannot have greater profit than j: it would have been processed earlier, and t was free then, so it could not have been rejected. Thus the exchange does not lower profit. If no slot is free for j, the optimal schedule agreeing on earlier placements cannot fit it either. Induction proves the greedy schedule optimal.

For (name,deadline,profit) jobs A=(2,100), B=(1,19), C=(2,27), D=(1,25), the profit order is A,C,D,B. A takes slot 2, C takes slot 1, and the others are rejected: total 127. Deadlines at most zero are infeasible; deadlines above n are capped at n. Empty input returns an empty list. The code uses O(n) slot storage and O(n²) worst-case time.

def schedule_jobs(jobs):
    slots = [None] * len(jobs)
    for job in sorted(jobs, key=lambda job: job[2], reverse=True):
        name, deadline, profit = job
        if profit <= 0:
            continue
        for t in range(min(deadline, len(jobs)) - 1, -1, -1):
            if slots[t] is None:
                slots[t] = job
                break
    return slots

jobs = [("A", 2, 100), ("B", 1, 19), ("C", 2, 27), ("D", 1, 25)]
assert schedule_jobs(jobs) == [jobs[2], jobs[0], None, None]
assert schedule_jobs([]) == []

Source

• GeeksforGeeks: Job Sequencing Problem

My reading · Opened notes are remembered in this browser.