Optimal algorithm for minimizing production cycle time of a printed circuit board assembly line

Abstract

The problem of the optimal allocation of components to a printed circuit board assembly line will several non-identical placement machines in series is considered. The objective is to achieve the highest throughput by minimizing the production cycle time of the assembly line. This problem can be formulated as a minimax approximation integer programming problem that belongs to the family of scheduling problems. The difficulty lies in the fact that this problem is proven to be NP-complete. All known algorithms 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. Detailed description of the algorithm is given together with examples that demonstrate its effectiveness.

Acknowledgement

The authors thank Professor B. Vilfan for providing the formal proof of NP-completeness for the problem (1–3).