An optimal algorithm for parallel NC machine scheduling problem

Suppose there are several machines with different performances and several parts to be processed. Each part requires a set of tools which have to be installed in the tool magazine with limited capacity. We consider a parallel NC machine scheduling problem which assigns each part to each machine so that the makespan can be minimized under tool magazine capacity constraints. This study proposes an optimal algorithm for solving the problem on the basis of the branch and bound method. First, the problem is formulated as a mixed 0–1 integer programming problem and a simple solution method of its Lagrangean relaxation problem is presented to determine its lower bound. After the lower bound is strengthened by using Lagrangean decomposition, a branch and bound method to solve the parallel NC machine scheduling problem is developed and its effectiveness is discussed through computational experiments.