Applying Dynamic Programming for Job Scheduling Problem

Problem

Suppose you have one machine and a set of $n$ jobs $a_1, a_2, ..., a_n$ to process on that machine. Each job $a_j$ has a processing time $t_j$ , a profit $p_j$ and a deadline $d_j$ . The machine can only do one job at a time, and job $a_j$ must run uninterruptedly for $t_j$ consecutive time units. If job $a_j$ is completed by its deadline $d_j$, you receive a profit $p_j$, but if it’s completed after its deadline, you receive a profit of $0$. Give a dynamic programming algorithm to find the schedule that obtains the maximum amount of profit, assuming that all processing times are integers between $1$ and $n$.

Solution

Now we provide the solution for the problem, considering that we have the following data:

Job (j)	Processing time ($t_j$)	Deadline ($d_j$)	Profit ($p_j$)
1	4	10	2
2	4	15	5
3	5	5	3
4	6	10	4

First Iteration

$𝑓_1[𝑎_1]= 2 \quad\quad\quad\quad 𝑘[1] = 1$
$𝑓_1[𝑎_2]= 5 \quad\quad\quad\quad 𝑘[2] = 2$
$𝑓_1[𝑎_3]= 3 \quad\quad\quad\quad 𝑘[3] = 3$
$𝑓_1[𝑎_4]= 4 \quad\quad\quad\quad 𝑘[4] = 4$

Second Iteration

$𝑓_2[𝑎_1,a_2]= max \big[f_1[a_1]+h_2(t_1+t_2), f_1[a_2]+h_1(t_1+t_2)\big]$
$\quad\quad\quad\quad =max\big[2+5,5+2\big]$
$\quad\quad\quad\quad =max\big[7,7\big]$
$\quad\quad\quad\quad =7$
$\quad k[1,2] = 1,2$

$𝑓_2[𝑎_1,a_3]= max \big[f_1[a_1]+h_3(t_1+t_3), f_1[a_3]+h_1(t_1+t_3)\big]$
$\quad\quad\quad\quad =max\big[2+0,3+2\big]$
$\quad\quad\quad\quad =max\big[2,5\big]$
$\quad\quad\quad\quad =5$
$\quad k[1,3] = 1$

$𝑓_2[𝑎_1,a_4]= max \big[f_1[a_1]+h_4(t_1+t_4), f_1[a_4]+h_1(t_1+t_4)\big]$
$\quad\quad\quad\quad =max\big[2+4,4+2\big]$
$\quad\quad\quad\quad =max\big[6,6\big]$
$\quad\quad\quad\quad =6$
$\quad k[1,4] = 1,4$

$𝑓_2[𝑎_2,a_3]= max \big[f_1[a_2]+h_3(t_2+t_3), f_1[a_3]+h_2(t_2+t_3)\big]$
$\quad\quad\quad\quad =max\big[5+0,3+5\big]$
$\quad\quad\quad\quad =max\big[5,8\big]$
$\quad\quad\quad\quad =8$
$\quad k[2,3] = 2$

$𝑓_2[𝑎_2,a_4]= max \big[f_1[a_2]+h_4(t_2+t_4), f_1[a_4]+h_2(t_2+t_4)\big]$
$\quad\quad\quad\quad =max\big[5+4,4+5\big]$
$\quad\quad\quad\quad =max\big[9,9\big]$
$\quad\quad\quad\quad =9$
$\quad k[2,4] = 2,4 $

$𝑓_2[𝑎_3,a_4]= max \big[f_1[a_3]+h_4(t_3+t_4), f_1[a_4]+h_3(t_3+t_4)\big]$
$\quad\quad\quad\quad =max\big[3+0,4+0\big]$
$\quad\quad\quad\quad =max\big[3,4\big]$
$\quad\quad\quad\quad =4$
$\quad k[3,4] = 3 $

Third Iteration

$𝑓_3[𝑎_1,a_2,a_3]= max \big[f_2[a_1,a_2]+h_3(t_1+t_2+t_3), f_2[a_1,a_3]+h_2(t_1+t_2+t_3), f_2[a_2,a_3]+h_1(t_1+t_2+t_3)\big]$
$\quad\quad\quad\quad\quad\quad =max\big[7+0,5+5,8+0\big]$
$\quad\quad\quad\quad\quad\quad =max\big[7,10,8\big]$
$\quad\quad\quad\quad\quad\quad =10$
$\quad\quad k[1,2,3] = 2$

$𝑓_3[𝑎_1,a_2,a_4]= max \big[f_2[a_1,a_2]+h_3(t_1+t_2+t_4), f_2[a_1,a_4]+h_2(t_1+t_2+t_4), f_2[a_2,a_4]+h_1(t_1+t_2+t_4)\big]$
$\quad\quad\quad\quad\quad\quad =max\big[7+0,6+5,9+0\big]$
$\quad\quad\quad\quad\quad\quad =max\big[7,11,9\big]$
$\quad\quad\quad\quad\quad\quad =11$
$\quad\quad k[1,2,4] = 2$

$𝑓_3[𝑎_1,a_3,a_4]= max \big[f_2[a_1,a_3]+h_3(t_1+t_3+t_4), f_2[a_1,a_4]+h_3(t_1+t_3+t_4), f_2[a_3,a_4]+h_1(t_1+t_3+t_4)\big]$
$\quad\quad\quad\quad\quad\quad =max\big[5+0,6+0,4+0\big]$
$\quad\quad\quad\quad\quad\quad =max\big[5,6,4\big]$
$\quad\quad\quad\quad\quad\quad =6$
$\quad\quad k[1,3,4] = 3$

$𝑓_3[𝑎_2,a_3,a_4]= max \big[f_2[a_2,a_3]+h_3(t_2+t_3+t_4), f_2[a_2,a_4]+h_3(t_2+t_3+t_4), f_2[a_3,a_4]+h_2(t_2+t_3+t_4)\big]$
$\quad\quad\quad\quad\quad\quad =max\big[8+0,9+0,4+5\big]$
$\quad\quad\quad\quad\quad\quad =max\big[5,9,9\big]$
$\quad\quad\quad\quad\quad\quad =9$
$\quad\quad k[2,3,4] = 2,3$

Fourth Iteration

$𝑓_4[𝑎_1,a_2,a_3,a_4]= max \big[f_3[𝑎_1,a_2,a_3]+h_4(t_1+t_2+t_3+t_4), f_3[𝑎_1,a_2,a_4]+h_3(t_1+t_2+t_3+t_4), f_3[𝑎_1,a_3,a_4]+$
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad h_2(t_1+t_2+t_3+t_4), f_1[a_2,a_3,a_4]+h_4(t_1+t_2+t_3+t_4)\big]$
$\quad\quad\quad\quad\quad\quad =max\big[10+0,11+0,6+0,9+0\big]$
$\quad\quad\quad\quad\quad\quad =max\big[10,11,6,9\big]$
$\quad\quad\quad\quad\quad\quad =11$
$\quad\quad k[1,2,3,4] = 3$

Solution

1 --> 4 --> 2 --> 3