Job Sequencing with Deadlines

1One machine, unit time, deadline, profit

A job-sequencing instance is n jobs and one machine. Every job takes exactly one time slot. Job i comes with a deadline d_i (an integer slot index) and a profit p_i paid only if the job is assigned a slot t with t \le d_i. A job that misses its deadline contributes 0. Two jobs cannot share a slot.

The machine's usable slots are 1,2,\ldots,D with D = \min(n, \max d_i). You cannot schedule more jobs than slots, and a deadline larger than n is no more useful than n.

Figure. Three unit slots on one machine. Five jobs will compete for these three cells.

Read one instance

1. JobsEach row is (id, d_i, p_i). Time is 1 for every job.
2. SlotsD = \min(n, \max d_i) cells on a single timeline.
3. ObjectiveMaximise the sum of profits of jobs that received a legal slot.

2Sort by profit, sit in the latest legal slot

The greedy order is decreasing profit. For the next job, scan slots d_i, d_i-1, \ldots, 1 and take the first one that is still free. If every legal slot is taken, reject the job.

Latest-fit is the rule that makes the order work. It parks a high-profit job as late as its deadline allows, so an earlier slot stays available for a later job in the list whose deadline is tighter. The sort is O(n \log n); each placement is a scan of at most D slots.

Same three slots; J1 occupies slot 2 and J3 occupies slot 1, as the ledger says.

Place one job

1. OrderJobs already sorted by p_i decreasing.
2. Scan right to leftTry slot d_i, then d_i-1, down to 1.
3. Take or skipFirst free slot wins. None free → profit 0 for this job.

Latest-slot placement

def job_sequence(jobs):
    jobs = sorted(jobs, key=lambda j: j['profit'], reverse=True)
    D = min(len(jobs), max(j['deadline'] for j in jobs))
    slot = [None] * (D + 1)
    for j in jobs:
        for t in range(min(D, j['deadline']), 0, -1):
            if slot[t] is None:
                slot[t] = j['id']
                break
    return slot[1:]

3Five jobs finish at profit 142

Running instance: J1 deadline 2 profit 100, J2 deadline 1 profit 19, J3 deadline 2 profit 27, J4 deadline 1 profit 25, J5 deadline 3 profit 15. Profit order J1, J3, J4, J2, J5. Slots: J1 in 2, J3 in 1, J4 and J2 rejected (slot 1 taken), J5 in 3.

Time order is J3, J1, J5. Profit 27+100+15=142. The two rejected jobs are the two cheapest; the greedy spent the three slots on the three profits that fit.

Figure. Final one-machine schedule: J3 in slot 1, J1 in slot 2, J5 in slot 3. Profits 27, 100, 15.

The five decisions

1. J1 then J3Slots 2 and 1 filled, 100 + 27.
2. J4, J2Only legal slot is 1, already taken — skip both.
3. J5Latest t \le 3 free is slot 3 — take 15.

Coding lab. Five jobs, profit 142 runs in the app, with checks on your output.

4Not earliest-finish activity selection

Activity selection maximises the count of non-overlapping intervals by sorting on earliest finish time. Job sequencing maximises profit of unit jobs under deadlines by sorting on profit and packing latest legal slots. The sort key, the objective, and the placement rule are all different.

Using earliest-finish on this instance is the wrong algorithm: the jobs are not intervals with start and finish, they are unit cells with a last-legal-cell. Multiprocessor makespan (identical processors) is a third problem — m machines, variable times, no per-job profit — and lives in the NP-scheduling topic.

No new Gantt — the three-row problem table is the comparison.