Group-scheduling problems in electronics manufacturing

This paper addresses the flowshop group-scheduling problems typically encountered in the assembly of printed circuit boards in electronics manufacturing. A mathematical programming model is formulated to capture the characteristics inherent to group-scheduling problems experienced in electronics manufacturing as well as those common to a wide range of group-scheduling problems encountered in other production environments. Several heuristics, each incorporating different components that underlie the tabu search concept, are developed to solve this strongly NP-hard problem effectively in a timely manner. In order to investigate the quality of the heuristic solutions with respect to tight lower bounds, an effective and efficient decomposition approach is developed. The problem is decomposed into a master problem and single-machine subproblems, and a column generation algorithm is developed to solve the linear programming relaxation of the master problem. Branching schemes, compatible with the column generation subproblems, are employed to partition the solution space when the solution to the linear programming relaxation is not integral. Furthermore, tabu search based fast heuristics are implemented to solve the subproblems, and an effective stabilization method is developed to accelerate the column generation approach. An experimental design with both fixed and random factors accompanied by rigorous statistical analyses of computational tests conducted on randomly generated test problems as well as on a large size real industry problem confirm the high performance of the proposed approach in identifying quality lower bounds and strongly suggest its flexibility and applicability to a wide range of real problems.