Integer programming approach to the printed circuit board grouping problem

Integer programming approach to the printed circuit board grouping problem

0.00 Avg rating0 Votes
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: , ,
Keywords: programming: integer
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.