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 2n 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 ∈ Sx }

Sx 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

Job Sequencing using Branch and Bound
Fig. (a): Variable tuple formulation of job sequencing problem
example of Job Sequencing using Branch and Bound
Fig. (b): Fixed tuple formulation of job sequencing problem

In the fixed tuple formulation, xi = 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 P2 + P3 = 16. The cost for node x is computed in a similar way.


Additional Reading: Read More

You may also like...

Leave a Reply

Your email address will not be published.