Job Sequencing Problem

The Job Sequencing Problem is a classic problem in computer science, often solved using greedy algorithms. The problem involves scheduling jobs to maximize profit when each job has a deadline and associated profit if it is completed on or before its deadline.

Problem Statement

Given a set of jobs where each job j has:

• A deadline d[j]
• A profit p[j] if it is completed on or before its deadline

The goal is to find a subset of jobs to perform that maximizes the total profit. Jobs must be completed within their deadlines.

Algorithm

1. Sort Jobs by Profit: Sort the jobs in descending order based on their profit.
2. Initialize the Schedule: Use an array (or another data structure) to keep track of the scheduled jobs. The size of this array is determined by the maximum deadline value.
3. Place Jobs in the Schedule:
   • For each job in the sorted list (from highest to lowest profit), try to place it in its latest possible slot, which is on or before its deadline and where no other job is placed.
   • If that slot is already taken, try to place the job in an earlier slot, continuing until either the job is placed or all slots up to the job’s deadline are filled.

Pseudocode

function jobSequencingWithDeadlines(jobs):
    sort jobs by profit in descending order
    initialize schedule array to None with size equal to the maximum deadline
    for each job in jobs:
        for slot in range(job.deadline, 0, -1):
            if schedule[slot] is None:
                schedule[slot] = job
                break
    return schedule

Considerations

• Complexity: The time complexity primarily depends on the sorting step, which is $O (n \log n)$, followed by the job placement, which in the worst case can take $O (n^2)$ when all jobs have late deadlines and each needs to be checked against all slots.
• Greedy Choice: The greedy choice here is to prioritize jobs with higher profits. This is because placing the highest profit jobs first ensures that they are not preempted by lower-profit jobs, maximizing the total profit.

Example

Imagine we have the following set of jobs, each with a deadline and a profit:

Job	Deadline	Profit
A	2	100
B	1	19
C	2	27
D	1	25
E	3	15

Steps to Solve

1. Sort Jobs by Profit:

   • Sorted by descending profit: A, C, D, B, E.

2. Initialize the Schedule:

   • We look at the maximum deadline, which is 3. So, we create a schedule array schedule[1..3] initialized to None.

3. Place Jobs in the Schedule:

   • Job A: Place in the last slot before or on its deadline (slot 2).
   • Job C: Slot 2 is taken by A, check slot 1.
   • Job D: Slot 1 is taken by C, check other slots but all are occupied within its deadline.
   • Job B: Cannot be placed since slot 1 is already occupied and it has no other slots.
   • Job E: Place in the last slot before or on its deadline (slot 3).

Final Schedule

Slot	Job
1	C
2	A
3	E

Explanation

• Job A is placed in slot 2 because it offers the highest profit.
• Job C, the next highest profit that can be scheduled by its deadline, is placed in slot 1.
• Job D and Job B cannot be scheduled since their possible slots are taken.
• Job E is placed in slot 3, as it's the only remaining job that fits within its deadline.

Result

• The scheduled jobs are A, C, and E, leading to a total profit of $100 + 27 + 15 = 142$.