Job Sequencing with Deadlines
Description
The Job Sequencing with Deadlines problem is a classic greedy algorithm problem where we have a set of jobs, each with a deadline and associated profit. The goal is to schedule the jobs to maximize the total profit, given that each job takes one unit of time and can only be performed before its deadline.
Each job can be scheduled in only one time slot, and only one job can be scheduled at any given time. If a job is scheduled after its deadline, the profit cannot be earned.
How It Works
- Sort all jobs in decreasing order of profit
- Initialize a result sequence with empty slots equal to the maximum deadline
- For each job in the sorted order:
- Find the latest available time slot before the job's deadline
- If such a slot exists, schedule the job in that slot
- Return the sequence of scheduled jobs
The greedy choice is to always consider the job with the highest profit first and schedule it as late as possible before its deadline. This ensures that we maximize profit while keeping earlier slots available for other jobs.
Visualization
Generate random jobs and click Start to begin visualization
Complexity Analysis
Time Complexity
-
Sorting: O(n log n)
- Sorting jobs by profit
-
Scheduling: O(n²)
- For each job, we may need to search for an available slot
- In the worst case, we check all slots for each job
-
Overall: O(n² log n)
- Dominated by the scheduling step
Space Complexity
-
Storage: O(n)
- Space to store the result sequence
- Space for sorting (implementation dependent)
Advantages and Disadvantages
Advantages
- Maximizes profit for scheduling problems
- Simple implementation
- Works well for problems with clear profit metrics
- Can be extended to handle variable job durations
Disadvantages
- Not optimal for all scheduling scenarios
- Quadratic time complexity in worst case
- Cannot handle jobs with dependencies
- Assumes unit time for each job
Implementation
def job_sequencing(jobs):
"""
Finds the sequence of jobs that maximizes profit.
Parameters:
jobs: list of tuples - Each tuple contains (job_id, deadline, profit)
Returns:
list of job_ids - Sequence of scheduled jobs
int - Total profit
"""
# Sort jobs in decreasing order of profit
sorted_jobs = sorted(jobs, key=lambda x: x[2], reverse=True)
# Find the maximum deadline
max_deadline = max(job[1] for job in jobs)
# Initialize result sequence with -1 (no job scheduled)
result = [-1] * max_deadline
slot_occupied = [False] * max_deadline
# Total profit
total_profit = 0
# Schedule jobs
for job in sorted_jobs:
job_id, deadline, profit = job
# Find a free time slot before the deadline
for slot in range(min(max_deadline, deadline) - 1, -1, -1):
if not slot_occupied[slot]:
result[slot] = job_id
slot_occupied[slot] = True
total_profit += profit
break
# Filter out unscheduled slots
scheduled_jobs = [job_id for job_id in result if job_id != -1]
return scheduled_jobs, total_profit
# Example usage
if __name__ == "__main__":
# Jobs as (job_id, deadline, profit)
jobs = [
(1, 4, 20), # Job 1 with deadline 4 and profit 20
(2, 1, 10), # Job 2 with deadline 1 and profit 10
(3, 1, 40), # Job 3 with deadline 1 and profit 40
(4, 1, 30), # Job 4 with deadline 1 and profit 30
(5, 3, 30) # Job 5 with deadline 3 and profit 30
]
scheduled_jobs, total_profit = job_sequencing(jobs)
print("Scheduled jobs:", scheduled_jobs)
print("Total profit:", total_profit)
# Expected output:
# Scheduled jobs: [3, 5, 1]
# Total profit: 90
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
class JobSequencing {
public:
// Function to find the maximum profit sequence of jobs
std::pair<std::vector<int>, int> scheduleJobs(const std::vector<std::tuple<int, int, int>>& jobs) {
int n = jobs.size();
// Sort jobs in decreasing order of profit
std::vector<std::tuple<int, int, int>> sortedJobs = jobs;
std::sort(sortedJobs.begin(), sortedJobs.end(),
[](const auto& a, const auto& b) {
return std::get<2>(a) > std::get<2>(b);
});
// Find the maximum deadline
int maxDeadline = 0;
for (const auto& job : jobs) {
maxDeadline = std::max(maxDeadline, std::get<1>(job));
}
// Initialize result sequence with -1 (no job scheduled)
std::vector<int> result(maxDeadline, -1);
std::vector<bool> slotOccupied(maxDeadline, false);
// Total profit
int totalProfit = 0;
// Schedule jobs
for (const auto& job : sortedJobs) {
int jobId = std::get<0>(job);
int deadline = std::get<1>(job);
int profit = std::get<2>(job);
// Find a free time slot before the deadline
for (int slot = std::min(maxDeadline, deadline) - 1; slot >= 0; slot--) {
if (!slotOccupied[slot]) {
result[slot] = jobId;
slotOccupied[slot] = true;
totalProfit += profit;
break;
}
}
}
// Filter out unscheduled slots
std::vector<int> scheduledJobs;
for (int jobId : result) {
if (jobId != -1) {
scheduledJobs.push_back(jobId);
}
}
return {scheduledJobs, totalProfit};
}
};
int main() {
// Jobs as (job_id, deadline, profit)
std::vector<std::tuple<int, int, int>> jobs = {
{1, 4, 20}, // Job 1 with deadline 4 and profit 20
{2, 1, 10}, // Job 2 with deadline 1 and profit 10
{3, 1, 40}, // Job 3 with deadline 1 and profit 40
{4, 1, 30}, // Job 4 with deadline 1 and profit 30
{5, 3, 30} // Job 5 with deadline 3 and profit 30
};
JobSequencing scheduler;
auto [scheduledJobs, totalProfit] = scheduler.scheduleJobs(jobs);
std::cout << "Scheduled jobs: ";
for (int jobId : scheduledJobs) {
std::cout << jobId << " ";
}
std::cout << std::endl;
std::cout << "Total profit: " << totalProfit << std::endl;
return 0;
}
using System;
using System.Collections.Generic;
using System.Linq;
public class JobSequencing
{
public (List<int> scheduledJobs, int totalProfit) ScheduleJobs(List<(int jobId, int deadline, int profit)> jobs)
{
// Sort jobs in decreasing order of profit
var sortedJobs = jobs.OrderByDescending(job => job.profit).ToList();
// Find the maximum deadline
int maxDeadline = jobs.Max(job => job.deadline);
// Initialize result sequence with -1 (no job scheduled)
int[] result = new int[maxDeadline];
for (int i = 0; i < maxDeadline; i++)
{
result[i] = -1;
}
bool[] slotOccupied = new bool[maxDeadline];
// Total profit
int totalProfit = 0;
// Schedule jobs
foreach (var job in sortedJobs)
{
// Find a free time slot before the deadline
for (int slot = Math.Min(maxDeadline, job.deadline) - 1; slot >= 0; slot--)
{
if (!slotOccupied[slot])
{
result[slot] = job.jobId;
slotOccupied[slot] = true;
totalProfit += job.profit;
break;
}
}
}
// Filter out unscheduled slots
List<int> scheduledJobs = result.Where(jobId => jobId != -1).ToList();
return (scheduledJobs, totalProfit);
}
public static void Main()
{
// Jobs as (job_id, deadline, profit)
var jobs = new List<(int jobId, int deadline, int profit)>
{
(1, 4, 20), // Job 1 with deadline 4 and profit 20
(2, 1, 10), // Job 2 with deadline 1 and profit 10
(3, 1, 40), // Job 3 with deadline 1 and profit 40
(4, 1, 30), // Job 4 with deadline 1 and profit 30
(5, 3, 30) // Job 5 with deadline 3 and profit 30
};
var scheduler = new JobSequencing();
var (scheduledJobs, totalProfit) = scheduler.ScheduleJobs(jobs);
Console.WriteLine("Scheduled jobs: " + string.Join(" ", scheduledJobs));
Console.WriteLine("Total profit: " + totalProfit);
}
}