Article ID: | iaor19942172 |
Country: | Netherlands |
Volume: | 6 |
Issue: | 1 |
Start Page Number: | 5 |
End Page Number: | 31 |
Publication Date: | Jan 1994 |
Journal: | International Journal of Flexible Manufacturing Systems |
Authors: | Bard Jonathan F., Feo Thomas A., Clayton Raymond W. |
Keywords: | programming: travelling salesman, programming: quadratic |
Populating printed circuit boards is one of the most costly and time-consuming steps in electronics assembly. At the beginning of each work order, three decisions are required: (1) a sequence must be specified for placing the individual components on the board; (2) tape reels must be assigned to positions on the magazine rack; and (3) a retrieval plan must be determined should the same component type be assigned to more than one magazine slot. Collectively, these problems can be modeled as a nonlinear integer program. In this paper, the authors develop a series of algorithms for solving each using an iterative two step approach. Initially, a placement sequence is generated with a weighted, nearest neighbor traveling salesman problem (TSP) heuristic; the two remaining problems are then formulated as a quadratic integer program and solved with a Lagrangean relaxation scheme. As a final step, the current magazine assignments are used to update the placement sequence, and the entire process is repeated. The ability to deal, at least in part, with simultaneous machine operations represents the major contribution of this work. The methodology was simulated for a set of boards obtained from Texas Instruments and theoretically compared with a heuristic currently in use.