Weighted job scheduling – dynamic programming

Weighted job scheduling

Suppose we have been give n jobs j1, j2,j3…jn with their start time s1,s2,… sn and finish time f1,f2, f3…fn. There is a value vi associated with each job. Ask is to find a schedule of these jobs such all jobs are compatible and we get maximum value.Two jobs are said to be compatible, if there execution time do not overlap. This problem is know as weighted job scheduling problem.

For example, we have four jobs as shown below:

Weighted job scheduling example

In above figure maximum value can be achieved by scheduling job 1 and job 4 which is value of 150. Notice that there one more schedule with compatible jobs (Job1, Job2 and Job 3), however, value we get by that schedule is only 100 which is less than what we got in earlier schedule.

There is strong urge to use greedy algorithm here. However, greedy algorithm works for this problem when value of all jobs is equal. Since value of jobs is different here, greedy algorithm fails.

Let’s consider brute force solution. First of all, sort all jobs based on finish time in increasing order. Now, for each job, decide if including it in schedule gives us maximum value or excluding it will give us maximum value. When we are including a job we have to check if it is compatible with other jobs which are included in schedule.

Determine compatibility of jobs

To determine compatibility quickly, we pre-calculate an array, called P such that

p(j) = largest index i < j such that job i is compatible with j.

For example:

weighted job scheduling

Now, let’s say OPT(j) represents the maximum value which we gain by adding jobs from 1 to j. As mentioned above, there are two cases:

Case 1: OPT selects job j. In this case we can not use incompatible jobs { p(j) + 1, p(j) + 2, …, j – 1 } – must include optimal solution to problem consisting of remaining compatible jobs 1, 2, …, p(j).

Case 2: OPT does not select job j. – must include optimal solution to problem consisting of remaining compatible jobs 1, 2, …, j-1

For case 1, we already have P[j] calculated. With P[j] already prepared, we know that we don’t have to check any job later than P[j] as all of them will be conflicting with current job. Recursive formula for calculating maximum value for n jobs will be:

OPT( j) = 0 if j = 0 
          max { vj + OPT( p(j) ), OPT(j-1)} otherwise

Weighted jobs scheduling- Recursive way

This recursive algorithm has exponential complexity as there are lot of subproblems which are calculated repeatedly. For example,

wieghted job scheduling using dynamic programming

Recursive execution tree for above problem would like

recursive execution of weighted jobs scheduling solution

From figure, we can see that there are subproblems which are being re-calculated. Typical way to avoid this repetition is to store solutions to subproblem, this method is called memoization. This is kind of a cache where results of subproblems are stored and looked into whenever required.

Dynamic programming implementation of weighted job scheduling

Run time complexity of dynamic programming approach for weighted job scheduling problem is O(nlogn) which is dominated by sort. Sorting takes O(nlogn) and calculation of maximum value takes O(n).
If we have pre-sorted input based on finish time, then this approach takes only O(n). Additional O(n) space is used for storing results of subproblems.

How about finding the solution itself, means to find actual jobs in schedule that gives us optimal value? This requires some post processing. Algorithm is as follows

Find-solution(j) : 
 if (j = 0) output nothing 
 else if (vj + Table[P(j)] > Table[j-1]) print j 
 else Find-Solution(j-1)

Please share if there is something wrong or missing. If you are interested in contributing to algorithms and me, please drop a mail and refer publishing at algorithms and me.