14.8 Job Sequencing with Deadlines
Many scheduling problems ask a simple question: > Given limited time and many competing jobs, which jobs should be performed?
14.8 Job Sequencing with Deadlines
Many scheduling problems ask a simple question:
Given limited time and many competing jobs, which jobs should be performed?
The answer is rarely "perform all of them." Deadlines, resource constraints, and limited execution windows force choices. The objective becomes selecting the subset that produces the greatest overall benefit.
The Job Sequencing with Deadlines problem is a classic example. Each job requires one unit of time, each job has a deadline, and each completed job earns a profit. The goal is to maximize total profit while ensuring that every scheduled job finishes before its deadline.
Unlike interval scheduling, where the objective is to maximize the number of activities, the objective here is to maximize value. This distinction changes the structure of the problem and leads to a different greedy strategy.
Problem
Given a collection of jobs:
| Job | Deadline | Profit |
|---|---|---|
| J1 | 2 | 100 |
| J2 | 1 | 19 |
| J3 | 2 | 27 |
| J4 | 1 | 25 |
| J5 | 3 | 15 |
Assumptions:
- Every job requires exactly one time slot.
- A job earns profit only if completed before its deadline.
- Only one job can execute at a time.
Determine a schedule that maximizes total profit.
Understanding the Constraints
The largest deadline determines the scheduling horizon.
For the example:
Deadline = 3
Available slots:
Slot 1
Slot 2
Slot 3
At most three jobs can be scheduled.
The challenge is deciding which jobs deserve those limited positions.
A First Attempt
One possible strategy is:
Schedule jobs by earliest deadline.
Sorted:
| Job | Deadline | Profit |
|---|---|---|
| J2 | 1 | 19 |
| J4 | 1 | 25 |
| J1 | 2 | 100 |
| J3 | 2 | 27 |
| J5 | 3 | 15 |
Result:
J2 J1 J5
Profit:
$$ 19 + 100 + 15 = 134 $$
This seems reasonable.
Unfortunately, it is not optimal.
Looking for a Better Rule
Observe the profits:
| Job | Profit |
|---|---|
| J1 | 100 |
| J3 | 27 |
| J4 | 25 |
| J2 | 19 |
| J5 | 15 |
Clearly J1 is extremely valuable.
If a scheduling decision causes J1 to be rejected, that decision is probably poor.
This suggests a different perspective:
Prioritize high-profit jobs.
Greedy Insight
Consider the most profitable job.
If it can be scheduled before its deadline, there is little reason to reject it in favor of a less profitable alternative.
The challenge is determining where to place it.
A crucial observation is:
Schedule each selected job as late as possible.
Doing so preserves earlier slots for jobs with tighter deadlines.
This leads to the classical greedy algorithm.
Greedy Algorithm
Step 1
Sort jobs by decreasing profit.
Step 2
Process jobs in that order.
Step 3
For each job, place it in the latest available slot that occurs before its deadline.
If no such slot exists, discard the job.
Example Walkthrough
Original jobs:
| Job | Deadline | Profit |
|---|---|---|
| J1 | 2 | 100 |
| J2 | 1 | 19 |
| J3 | 2 | 27 |
| J4 | 1 | 25 |
| J5 | 3 | 15 |
Sorted by profit:
| Job | Deadline | Profit |
|---|---|---|
| J1 | 2 | 100 |
| J3 | 2 | 27 |
| J4 | 1 | 25 |
| J2 | 1 | 19 |
| J5 | 3 | 15 |
Schedule J1
Latest available slot before deadline 2:
Slot 2
Schedule:
| Slot | Job |
|---|---|
| 1 | - |
| 2 | J1 |
| 3 | - |
Schedule J3
Deadline:
2
Slot 2 already occupied.
Try Slot 1.
Schedule:
| Slot | Job |
|---|---|
| 1 | J3 |
| 2 | J1 |
| 3 | - |
Schedule J4
Deadline:
1
Slot 1 occupied.
Reject.
Schedule J2
Deadline:
1
Slot 1 occupied.
Reject.
Schedule J5
Deadline:
3
Slot 3 available.
Schedule:
| Slot | Job |
|---|---|
| 1 | J3 |
| 2 | J1 |
| 3 | J5 |
Total profit:
$$ 27 + 100 + 15 = 142 $$
This is optimal.
Why Schedule Jobs Late?
Suppose J1 has deadline 5.
Placing it in Slot 1 wastes flexibility.
A future job might have deadline 1 and no alternative slot.
Placing J1 in the latest feasible position preserves more scheduling options.
This mirrors the reasoning behind interval scheduling:
Preserve future opportunities whenever possible.
Correctness Sketch
Consider the highest-profit job.
Suppose an optimal schedule excludes it even though a feasible slot exists.
Replace a lower-profit scheduled job with the higher-profit job.
Total profit increases.
The original schedule could not have been optimal.
Therefore some optimal schedule must contain the highest-profit feasible job.
The greedy choice is safe.
Scheduling the job as late as possible further preserves flexibility for remaining jobs.
Repeating this reasoning constructs an optimal schedule.
Naive Implementation
For each job:
- Search backward from its deadline.
- Find the latest free slot.
- Schedule the job.
Go
type Job struct {
ID string
Deadline int
Profit int
}
Core scheduling loop:
for _, job := range jobs {
for slot := job.Deadline; slot >= 1; slot-- {
if schedule[slot] == nil {
schedule[slot] = &job
break
}
}
}
Complexity Analysis
Let:
$$ n $$
be the number of jobs.
Sorting:
$$ O(n \log n) $$
Slot search:
$$ O(n^2) $$
in the worst case.
Total:
$$ O(n^2) $$
For moderate input sizes, this is usually acceptable.
Optimizing with Union-Find
The backward search can be accelerated using a disjoint-set structure.
Each slot points to the nearest available slot before it.
After assigning a slot, union operations update availability.
Complexity becomes:
$$ O(n \log n) $$
or nearly linear with path compression.
This optimization is common in competitive programming and large-scale scheduling systems.
Common Mistakes
Scheduling Earliest Available Slot
This often blocks jobs with tighter deadlines.
Sorting by Deadline
Deadline order does not maximize profit.
Sorting by Duration
All jobs already have equal duration.
The ordering provides no useful information.
Ignoring Empty Late Slots
Late unused slots may still be valuable for future jobs.
The algorithm should always search from the deadline backward.
Real-World Applications
Manufacturing
Select the most profitable orders that can be completed on time.
Cloud Computing
Allocate compute windows to high-value workloads.
Advertisement Scheduling
Place advertisements into limited broadcast slots.
Warehouse Operations
Prioritize shipments with varying revenue impact.
Project Management
Allocate scarce resources to high-value tasks.
In each case, the central question is identical:
Which tasks deserve the limited available time?
Relationship to Previous Recipes
Interval scheduling chooses:
Earliest finishing activity
Fractional knapsack chooses:
Highest value density
Job sequencing chooses:
Highest profit job
The specific rule changes, but the design process remains consistent:
- Identify the most valuable local choice.
- Show that choice can appear in an optimal solution.
- Preserve future flexibility.
- Repeat until no choices remain.
Takeaway
Job Sequencing with Deadlines is a classic greedy optimization problem in which jobs are sorted by profit and scheduled as late as possible before their deadlines. The strategy works because high-profit jobs should never be displaced by lower-profit alternatives when a feasible slot exists, and late placement preserves opportunities for future jobs. The resulting algorithm is simple, efficient, and widely applicable to real-world scheduling and resource-allocation systems.