Job Sequencing with Deadlines

Introduction

The Job Sequencing problem with deadlines is a classic greedy scheduling problem. We have a set of jobs, each with a profit and a deadline. Each job takes one unit of time to complete, and only one job can be scheduled at a time. The objective is to select and schedule a subset of jobs such that each selected job finishes by its deadline and the total profit is maximized.

The greedy strategy is intuitive: prioritize high-profit jobs and assign each to the latest available time slot before its deadline. This "latest slot" strategy is optimal because it preserves earlier slots for jobs with tighter deadlines, maximizing flexibility for future assignments.

Problem Definition

Given:

• n jobs, each with a profit p_i and a deadline d_i
• Each job takes exactly 1 unit of time
• Only one job can run at a time
• Job i earns profit p_i only if completed by time d_i

Find a subset of jobs and a schedule (assignment of jobs to time slots) that maximizes the total profit. A job with deadline d can be scheduled in any slot from 1 to d.

Greedy Approach

procedure JobSequencing(jobs): sort jobs by profit in decreasing order maxDeadline = max(d_i for all jobs) slots = array of size maxDeadline, all empty totalProfit = 0 scheduledJobs = [] for each job j in sorted order: // Find the latest available slot before j's deadline for t from min(j.deadline, maxDeadline) down to 1: if slots[t] is empty: slots[t] = j totalProfit = totalProfit + j.profit scheduledJobs.add(j) break return scheduledJobs, totalProfit

The greedy choice of always considering the highest-profit job first is optimal because assigning a high-profit job to its latest possible slot gives lower-profit jobs the maximum opportunity to find earlier slots. This is an instance of the exchange argument: any solution not following this strategy can be improved by swapping assignments.

Slot Assignment Strategy

When assigning a job with deadline d, we search for an empty slot from d down to 1. The "latest available slot" strategy is critical:

• Assigning a job to an earlier slot than necessary wastes the later slot that might be the only option for a future job.
• By using the latest slot, we preserve flexibility for jobs with earlier deadlines.
• If no slot is available (all slots from 1 to d are occupied), the job is skipped.

The naive slot search takes O(n) per job, giving O(n^2) total. This can be improved to nearly O(n) using a Disjoint Set Union (DSU) data structure.

Worked Example

Jobs (sorted by profit):

Step 1: J1 (profit=100, deadline=2): slot 2 is empty. Assign to slot 2.

Step 2: J2 (profit=80, deadline=1): slot 1 is empty. Assign to slot 1.

Step 3: J3 (profit=50, deadline=2): slots 2 and 1 both occupied. Skip.

Step 4: J4 (profit=40, deadline=3): slot 3 is empty. Assign to slot 3.

Step 5: J5 (profit=20, deadline=1): slot 1 occupied. Skip.

Result: Schedule: [J2, J1, J4]. Total profit: 80 + 100 + 40 = 220.

Complexity Analysis

The sorting step takes O(n log n). The slot assignment takes O(n^2) naively or O(n * alpha(n)) with DSU, where alpha is the inverse Ackermann function (effectively constant).

Implementation

def job_sequencing(jobs): # jobs is a list of (job_id, deadline, profit) jobs.sort(key=lambda x: x[2], reverse=True) max_deadline = max(d for _, d, _ in jobs) slots = [None] * (max_deadline + 1) total_profit = 0 scheduled = [] for job_id, deadline, profit in jobs: for t in range(min(deadline, max_deadline), 0, -1): if slots[t] is None: slots[t] = job_id total_profit += profit scheduled.append(job_id) break return scheduled, total_profit# Examplejobs = [("J1", 2, 100), ("J2", 1, 80), ("J3", 2, 50), ("J4", 3, 40), ("J5", 1, 20)]scheduled, profit = job_sequencing(jobs)print(f"Jobs: Jobs successfully completed within their assigned time constraints, Profit: Maximize total profit by selecting the optimal combination of jobs that can be completed within their deadlines")# Output: Jobs: ['J1', 'J2', 'J4'], Profit: 220

Union-Find Optimization

The O(n^2) slot search can be optimized using a Disjoint Set Union data structure. The idea is to maintain a parent pointer for each slot. Initially, parent[t] = t for all slots. When slot t is filled, we set parent[t] = t-1, effectively pointing to the next available earlier slot.

procedure FindSlot(t): if parent[t] == t: return t parent[t] = FindSlot(parent[t]) // path compression return parent[t]procedure JobSequencingDSU(jobs): sort jobs by profit descending maxDeadline = max(d_i) parent = [i for i in range(maxDeadline + 1)] for each job j: slot = FindSlot(min(j.deadline, maxDeadline)) if slot > 0: schedule j at slot Union(slot, slot - 1) // parent[slot] = slot - 1

With path compression and union by rank, each find operation takes amortized O(alpha(n)) time, making the total algorithm O(n log n) dominated by sorting.

Variants and Applications

• Minimizing Lateness: Instead of maximizing profit, minimize the maximum lateness across all jobs. Solved optimally by the Earliest Deadline First (EDF) greedy strategy.
• Weighted Job Scheduling: Jobs have arbitrary processing times and profits. This requires dynamic programming (similar to weighted activity selection).
• Multiple Machines: When k machines are available, up to k jobs can run simultaneously. The greedy approach extends naturally.
• Preemptive Scheduling: If jobs can be interrupted and resumed, different algorithms (like EDF for real-time systems) apply.
• Online Scheduling: Jobs arrive over time and must be scheduled without knowledge of future arrivals. Competitive analysis measures the quality of online algorithms.

Job sequencing with deadlines is a special case of the weighted matroid intersection problem. The set of feasible schedules forms a matroid, and the greedy algorithm on matroids always produces an optimal solution for maximizing a linear objective function.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. "Introduction to Algorithms." MIT Press, Chapter 16, 2009.
• Kleinberg, J. and Tardos, E. "Algorithm Design." Addison-Wesley, Chapter 4, 2005.
• Lawler, E. L. "Optimal Sequencing of a Single Machine Subject to Precedence Constraints." Management Science, vol. 19, 1973, pp. 544-546.
• Pinedo, M. L. "Scheduling: Theory, Algorithms, and Systems." Springer, 5th edition, 2016.