A Lower Bound Based Branch-and-Price Mechanism in the Integration of Kitting and Assembly Operations

摘要

A new scheduling problem in the assembly of printed circuit boards (PCBs) is investigated in this paper. The technical constraint of kitting all boards before starting the assembly operation is paid attention to by introducing the concept of "integrating external and internal setups". This essentially results in the development of a dynamic PCB assembly system, as a result of which, has some characteristics of just-in-time manufacturing. Previous research in this area has always been simplified by introducing either sequence-independent setup time or sequence-dependent setup time, at best. In this research, the setup has been carefully investigated and correctly captured by introducing the carryover sequence-dependent setup time. Since the problem investigated is NP-hard, the development of heuristic approaches is needed; however, the effectiveness of the heuristics is questionable in instances where the optimal solution is not available. To combat this difficulty, a lower bound based on the branch-and-price mechanism is developed and is compared against the solutions found by heuristics. To make the process of identifying the lower bound more efficient, a heuristic is employed to support the column generation approach at each node of the branch-and-price tree.