摘要：We consider the problem of optimal allocation of components to a printed circuit board (PCB) assembly line which has several nonidentical placement machines in series. The objective is to achieve the highest production throughput by minimizing the cycle time of the assembly line. This problem can be formulated as a minimax approximation integer programming model that belongs to the family of scheduling problems. The difficulty lies in the fact that this model is proven to be \emph{NP}-complete. All known algorithms that solve the NP-complete problems are exponential and work only if the number of variables is reasonably small. This particular problem, however, has properties that allow the development of a very efficient type of branch-and-bound based optimal algorithm that works for problems with a practically useful number of variables.
