Article ID: | iaor20053194 |
Country: | United Kingdom |
Volume: | 43 |
Issue: | 8 |
Start Page Number: | 1667 |
End Page Number: | 1684 |
Publication Date: | Jan 2005 |
Journal: | International Journal of Production Research |
Authors: | Kim D., Park S., Yu S. |
Keywords: | programming: integer |
A printed circuit board (PCB) grouping problem arising from the electronics industry is considered. Given a surface-mounting device with a number of component feeders and several types of PCBs to be produced, the problem is how to group the PCBs so that the total set-up time for component feeders is minimized. The problem is formulated as an integer-programming problem and a column generation approach is proposed to solve it. In this approach, the original problem is decomposed into a master problem and a column-generation subproblem. Starting with a few columns in the master problem, new columns are generated successively by solving the subproblem optimally. To solve the subproblem, a branch-and-cut approach is used. To solve the master problem, a branch-and-bound algorithm is used with the generated columns. However, a branching strategy is also proposed that maintains consistency in the column-generation procedure after branching. Computational experiments show that the solution approach gives high-quality solutions in reasonable computing time.