JOB SELECTION ALGORITHM

Introduction
•The primary algorithm for solving the "job selection" problem
(formally known as the Job Sequencing Problem with
Deadlines) is a greedy algorithm that uses sorting and data
structures like arrays or priority queues to maximize total profit
•Job scheduling algorithm is applied to schedule the jobs on a
single processor to maximize the profits.
•The greedy approach of the job scheduling algorithm states
that, Given n number of jobs with a starting time and ending
time, they need to be scheduled in such a way that maximum
profit is received within the maximum deadline.
Set of jobs with deadlines and profits are taken as an input with the job
scheduling algorithm and scheduled subset of jobs with maximum profit
are obtained as the final output.
Algorithm
Step1 − Find the maximum deadline value from the input set of jobs.
Step2 − Once, the deadline is decided, arrange the jobs in descending
order of their profits.
Step3 − For each job in the sorted order, find the latest available time slot
that is less than or equal to its deadline and assign the job to that slot.
Step4 − The selected set of jobs are the output.
Example
• Consider the following tasks with their deadlines and profits.
Schedule the tasks in such a way that they produce maximum profit
after being executed −

S. No. 1 2 3 4 5
Jobs J1 J2 J3 J4 J5
Deadlines 2 2 1 3 4
Profits 20 60 40 100 80
Step 1
• Find the maximum deadline value, dm, from the deadlines given.
• dm = 4
• This means we have 4 time slots available: [1], [2], [3], [4]
Step 2
• Arrange the jobs in descending order of their profits

S. No. 1 2 3 4 5
Jobs J4 J5 J2 J3 J1
Deadlines 3 4 2 1 2
Profits 100 80 60 40 20
 Step 3
Select jobs greedily, placing each in the latest available time
slot that does not exceed its deadline.
Iteration 1: J4 Iteration 3: J2 (Profit = 60, Deadline = 2)
(Profit = 100, Deadline = 3) • Find the latest free slot ≤ 2. Slot 2 is free, so
• Find the latest free slot ≤ 3. Slot 3 assign J2 to slot 2.
is free, so assign J4 to slot 3. • Slots: [_, J2, J4, J5]
• Slots: [_, _, J4, _] • Total Profit = 180 + 60 = 240
• Total Profit = 100 Iteration 4: J3 (Profit = 40, Deadline = 1)
Iteration 2: J5 • Find the latest free slot ≤ 1. Slot 1 is free, so
(Profit=80,Deadline=4) assign J3 to slot 1.
• Find the latest free slot ≤ 4. Slot 4 • Slots: [J3, J2, J4, J5]
is free, so assign J5 to slot 4. • Total Profit = 240 + 40 = 280
• Slots: [_, _, J4, J5] Iteration 5: J1 (Profit = 20, Deadline = 2)
• Total Profit = 100 + 80 = 180 • Find the latest free slot ≤ 2. Slots 1 and 2 are
already occupied. J1 cannot be scheduled.
Step 4
• All jobs have been considered. The algorithm terminates.
Final Result:
• The optimal sequence of jobs scheduled within their
deadlines is {J3, J2, J4, J5} (executed in time slots 1, 2, 3, 4
respectively) with the maximum profit of 280.
• Maximum Profit: 40 + 60 + 100 + 80 = 280

Time Slot 1 2 3 4
Job J3 J2 J4 J5
Profit 40 60 100 80
Data Structures Used….
• Array (or Boolean Array): Used to represent and manage the time
slots. This allows for efficient checking and marking of available slots.
• Struct/Class: A custom data structure to store each job's ID, deadline,
and profit together.
• Sorting: The jobs array is sorted (typically using an efficient algorithm
like Quicksort or Mergesort) by profit in descending order, which has
a time complexity of O(n log n).
• Priority Queue (Min-Heap): An optimized approach uses a min-heap
to keep track of selected jobs' profits while sorting by deadline. This
can improve efficiency in certain scenarios.
Complexity
• The standard greedy algorithm has a time complexity of O(n²),
primarily due to the nested loops used to find the latest available slot
for each job after sorting.
• A more efficient implementation using a Disjoint Set Union (DSU) data
structure can optimize the process of finding free slots, reducing the
time complexity.
Similar Job Scheduling Algorithms…
The term "job selection algorithm" might also refer to general
operating system process scheduling, which uses different algorithms:
• First-Come, First-Served (FCFS): Processes are executed in the order
of arrival.
• Shortest Job First (SJF): The process with the smallest execution time
is run first. This minimizes average waiting time.
• Priority Scheduling: Jobs are assigned priority levels, and the highest
priority job is executed first.
• Round Robin: Each process is given a fixed time slice (quantum) in a
cyclic manner, ensuring fairness in time-sharing systems.
 Examples….
1.
Input: deadline[] = [4, 1, 1, 1], profit[] = [20, 10, 40, 30]
Output: [2, 60]

Explanation: Job 1 (profit 20, deadline 4) can be scheduled. Among the three
jobs with deadline 1, only one fits, so we pick the highest profit (40). Hence, 2
jobs with total profit = 60.

2.
Input: deadline[] = [2, 1, 2, 1, 1], profit[] = [100, 19, 27, 25, 15]
Output:
[2, 127]

Explanation: Picking the job with profit 100 (deadline 2) and the job with profit
27 (deadline 2); they can occupy the two available slots before deadline 2. Thus 2
jobs are scheduled for a maximum total profit of 127.
3.
• Input:

• Output:
 ALGORITHM
JobSelection(Jobs, n)
// Input: List of jobs, each with a profit and deadline
// Output: Maximum profit and the sequence of jobs
// 1. Sort all jobs in descending order of profit
SORT Jobs by Profit DESCENDING
// 2. Find the maximum deadline to determine total slots
maxDeadline = FIND_MAX_DEADLINE(Jobs)
// 3. Initialize slots (e.g., -1 indicates empty)

SLOTS = ARRAY of size maxDeadline, filled with -1

FOR i = 0 TO n-1 DO
// Find a free slot for this job, starting from its deadline. Jobs need to be done by end of slot time)
FOR j = MIN(maxDeadline, Jobs[i].deadline) DOWNTO 1 DO
IF SLOTS[j] == -1 THEN
SLOTS[j] = Jobs[i].id // Schedule job
totalProfit = totalProfit + Jobs[i].profit
countJobs = countJobs + 1
 ALGORITHM
BREAK // Job scheduled
END IF
END FOR
END FOR
RETURN totalProfit, SLOTS
END