Lower bound development in a flow shop electronic assembly problem with carryover sequence-dependent setup time

A flow shop group-scheduling problem in the assembly of printed circuit boards (PCBs) is addressed in this paper. We have developed search algorithms yet their quality cannot be attested to when optimal solutions or lower bounds are unavailable. A very effective and efficient lower-bounding mechanism based on the underlying concepts of column generation and branch-and-price is developed. The problem remains so complex even after decomposition. Thus, optimal properties and strategies are developed to facilitate efficiently solving the sub problems. Accompanied by an experimental design and statistical analysis, comprehensive computational tests for a wide range of problems are carried out. The findings suggest that the lower bound and search algorithms are very effective even for large-size problem instances.