Five jobs need to be done on a certain machine. However, the setup time for each job depends upon which job immediately preceded it, as shown by the following table:

The objective is to schedule the sequence of jobs that minimizes the sum of the resulting setup times.

(a) Design a branch-and-bound algorithm for sequencing problems of this type by specifying how the branch, bound, and fathoming steps would be performed.

(b) Use this algorithm to solve this problem.

12.6-9.* Consider the following nonlinear BIP problem.

Maximize Z 80x1 60x2 40x3 20x4

 (7x1 5x2 3x3 2x4)

2

, subject to xj is binary, for j 1, 2, 3, 4.

Given the value of the first k variables x1, . . . , xk, where k 0, 1, 2, or 3, an upper bound on the value of Z that can be achieved by the corresponding feasible solutions is k

j1 cjxj  

k j1 djxj



2 4

jk1 max 0, cj  

k i1 dixi dj



2

 

k i1 dixi



2

, where c1 80, c2 60, c3 40, c4 20, d1 7, d2 5, d3 3, d4 2. Use this bound to solve the problem by the branch-andbound technique.