A branch and bound algorithm for unrelated parallel-machine scheduling problem

Suppose there are several machines of different performances and several jobs to be processed. Though each job can be processed by a given machine, the processing time depends on the machine used. Also suppose that there is no precedence relation among jobs. Then, the problem which assigns each job to each machine so that the makespan can be minimized is called the unrelated parallel-machine scheduling problem. This study proposes an optimization algorithm of the problem based on the branch and bound method. First, the problem is formulated as a mixed 0-1 integer programming problem (P) to confirm several properties related to the problem (P). Next, a simple algorithm to determine the lower bound of (P) is presented on the basis of the properties. Finally, a branch and bound method to solve the problem (P) is constructed, and its effectiveness is discussed through computational experiments. [In Japanese.]