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.

Transcribed Image Text:

Setup Time Job 2 None 45 8 94 7 12 10 9 10 14 11 12 10 Immediatehy Preceding Job 2 10 1 7 8 15 4 12 9 8 16 _