Job Sequencing using Branch and Bound

Job Sequencing using Branch and Bound: Given n jobs with profit, execution time, and deadline, achieve the schedule which maximizes the profit.

We will solve the problem using the FIFO branch and bound with the variable tuple and fixed tuple representations. Each job i is represented by the tuple (Pi, di, ti), where Pi, di, and ti represent profit, deadline, and execution time associated with job i. If job i is completed on or before its deadline, profit Pi is earned. But if the job i finish after its deadline, then a penalty Pi will incur. The brute force method finds 2ⁿ schedules for n jobs and finds the best from them. Branch and bound is a more efficient way of finding the optimal schedule.

Examples on Job Sequencing using Branch and Bound

Example: Select optimal subset J with an optimal penalty for the following data. What will be the penalty corresponding to the optimal solution?

Job	Pi	di	ti
1	5	1	1
2	10	3	2
3	6	2	1
4	3	1	1

Solution:

The cost function for node x in state space tree for job sequencing problem is defined as,

\[ \hat{c}(x) = \sum_{i<m ; & ; i notin S_x} P_i \]

Where, m = max{i  |  i ∈ S_x }

S_x is the subset of jobs selected at node x.

Upper bound u(x) for node x is defined as,

\[ u(x) = sum_{i notin S_x} P_i \]

Computation of cost and bound for each node using variable tuple size is shown in the following table.

Node	Sx = Set of selected jobs at node x	m = max(i  |  i ∈ Sx)	\[ hat{c}(x) = sum_{i<m ; & ; i notin S_x} P_i \]	\[ u(x) = sum_{i notin S_x} P_i \]
1	{ }	1	0	5 + 10 + 6 + 3 = 24
2	{1}	1	0	10 + 6 + 3 = 19
3	{2}	2	5	5 + 6 + 3 = 14
4	{3}	3	5 + 10 = 15	5 + 10 + 3 = 18
5	{4}	4	5 + 10 + 6 = 21	5 + 10 + 6 = 21
6	{1, 2}	2	0	6 + 3 = 9
7	{1, 3}	3	10	10 + 3 = 13
8	{1, 4}	4	10 + 6 = 16	10 + 6 = 16
9	{2, 3}	3	5	5 + 3 = 8
10	{2, 4}	4	5 + 6 = 11	5 + 6 = 11
11	{3, 4}	4	5 + 10 = 15	5 + 10 = 15

State-space tree for variable tuple formulation and fixed tuple formulation is depicted in Fig. (a) and Fig. (b), respectively

In the fixed tuple formulation, x_i = 1 indicates the inclusion of job i, and xi = 0 indicates the exclusion of job i. For example, at node 6, job 1 is omitted and job 2 is selected, so the penalty at that node is 5. At node 11, job 1 is included but jobs 2 and 3 are excluded, so the penalty incurred at node 11 is P₂ + P₃ = 16. The cost for node x is computed in a similar way.

---

Additional Reading: Read More