Job scheduling is the problem of scheduling jobs out of a set of N jobs on a single processor which maximizes profit as much as possible. Consider N jobs, each taking unit time for execution. Each job is having some profit and deadline associated with it. Profit earned only if the job is completed on or before its deadline. Otherwise, we have to pay a profit as a penalty. Each job has deadline di ≥ 1 and profit pi ≥ 0. At a time, only one job can be active on the processor.

The job is feasible only if it can be finished on or before its deadline. A feasible solution is a subset of N jobs such that each job can be completed on or before its deadline. An optimal solution is a solution with maximum profit. The simple and inefficient solution is to generate all subsets of the given set of jobs and find the feasible set that maximizes the profit. For N jobs, there exist 2N schedules, so this brute force approach runs in O(2N) time.

However, the greedy approach produces an optimal result in fairly less time. As each job takes the same amount of time, we can think of the schedule S consisting of a sequence of job slots 1, 2, 3, …, N, where S(t) indicates job scheduled in slot t. Slot t has a span of (t – 1) to t. S(t) = 0 implies no job is scheduled in slot t.

Schedule S is an array of slots S(t), S(t) ∈ {1, 2, 3, …, N} for each t ∈ {1, 2, 3, …, N}

Schedule S is feasible if,

  • S(t) = i, then t ≤ di (Scheduled job must meet its deadline)
  • Each job can be scheduled at max once.

Our goal is to find a feasible schedule S which maximizes the profit of scheduled job. The goal can be achieved as follow: Sort all jobs in decreasing order of profit. Start with the empty schedule, select one job at a time and if it is feasible then schedule it in the latest possible slot.

Algorithm for Job Scheduling

Algorithm for job scheduling is described below:

Algorithm JOB_SCHEDULING( J, D, P )
// Description : Schedule the jobs using the greedy approach which maximizes the profit

// Input : 		 
J: Array of N jobs
D: Array of the deadline for each job
P: Array of profit associated with each job

// Output : Set of scheduled job which gives maximum profit

Sort all jobs in J in decreasing order of profit
S ← Φ	// S is set of scheduled jobs, initially it is empty 
SP ← 0	// Sum is the profit earned 
for i ← 1 to N do
  if Job J[i] is feasible then
    Schedule the job in the latest possible free slot meeting its deadline.
    S ← S ∪ J[i]
    SP ← SP + P[i]
  end
end

Complexity Analysis of Job Scheduling

Simple greedy algorithm spends most of the time looking for the latest slot a job can use.  On average, N jobs search N/2 slots. This would take O(N2) time.

However, with the use of set data structure (find and union), the algorithm runs nearly in O(N) time.

Examples

Problem: Solve the following job scheduling with deadlines problem using the greedy method. Number of jobs N = 4. Profits associated with Jobs : (P1, P2, P3, P4) = (100, 10, 15, 27). Deadlines associated with jobs (d1, d2, d3, d4) = (2, 1, 2, 1)

Solution:

Sort all jobs in descending order of profit.

So, P = (100, 27, 15, 10), J = (J1, J4, J3, J2) and D = (2, 1, 2, 1). We shall select one by one job from the list of sorted jobs, and check if it satisfies the deadline. If so, schedule the job in the latest free slot. If no such slot is found, skip the current job and process the next one. Initially,

Job Scheduling

Profit of scheduled jobs, SP = 0

Iteration 1:

Deadline for job J1 is 2. Slot 2 (t = 1 to t = 2) is free, so schedule it in slot 2. Solution set S= {J1}, and Profit SP = {100}

Job Scheduling example

Iteration 2:

Deadline for job J4 is 1. Slot 1 (t = 0 to t = 1) is free, so schedule it in slot 1.

Solution set S = {J1,J4}, and Profit SP = {100, 27}

Job Scheduling

Iteration 3:

Job J3 is not feasible because first two slots are already occupied and if we schedule J3 any time later t = 2, it cannot be finished before its deadline 2. So job J3 is discarded,

Solution set S = {J1,J4}, and Profit SP = {100, 27}

Iteration 4:

Job J2 is not feasible because first two slots are already occupied and if we schedule J2 any time later t = 2, it cannot be finished before its deadline 1. So job J2 is discarded,

Solution set S = {J1,J4}, and Profit SP = {100, 27}

With the greedy approach, we will be able to schedule two jobs {J1, J4}, which gives a profit of 100 + 27 = 127 units.

Problem: Solve the following instance of “job scheduling with deadlines” problem : n = 7, profits (p1, p2, p3, p4, p5, p6, p7) = (3, 5, 20, 18, 1, 6, 30) and deadlines (d1,  d2, d3, d4, d5, d6, d7) = (1, 3, 4, 3, 2, 1, 2). Schedule the jobs in such a way to get maximum profit.

Solution:

Given that,

Jobsj1j2j3j4j5j6j7
Profit3520181630
Deadline1343212

Sort all jobs in descending order of profit.

So, P = (30, 20, 18, 6, 5, 3, 1), J = (J7, J3, J4, J6, J2, J1, J5) and D = (2, 4, 3, 1, 3, 1, 2). We shall select one by one job from the list of sorted jobs J, and check if it satisfies the deadline. If so, schedule the job in the latest free slot. If no such slot is found, skip the current job and process the next one. Initially,

Job sequencing

Profit of scheduled jobs, SP = 0

Iteration 1:

Deadline for job J7 is 2. Slot 2 (t = 1 to t = 2) is free, so schedule it in slot 2. Solution set S = {J7}, and Profit SP = {30}

Job sequencing example

Iteration 2:

Deadline for job J3 is 4. Slot 4 (t = 3 to t = 4) is free, so schedule it in slot 4. Solution set S = {J7, J3}, and Profit SP = {30, 20}

Iteration 3:

Deadline for job J4 is 3. Slot 3 (t = 2 to t = 3) is free, so schedule it in slot 3.

Solution set S = {J7, J3, J4}, and Profit SP = {30, 20, 18}

Iteration 4:

Deadline for job J6 is 1. Slot 1 (t = 0 to t = 1) is free, so schedule it in slot 1.

Solution set S = {J7, J3, J4, J6}, and Profit

SP = {30, 20, 18, 6}

First, all four slots are occupied and none of the remaining jobs has deadline lesser than 4. So none of the remaining jobs can be scheduled. Thus, with the greedy approach, we will be able to schedule four jobs {J7, J3, J4, J6}, which give a profit of (30 + 20 + 18 + 6) = 74 units.


Additional Reading: Click to read