Article ID: | iaor19911324 |
Country: | Germany |
Volume: | 35 |
Start Page Number: | 189 |
End Page Number: | 195 |
Publication Date: | Feb 1991 |
Journal: | Mathematical Methods of Operations Research (Heidelberg) |
Authors: | Grtschel M., Jnger M., Reinelt G. |
Printed circuit board production is one of the basic technologies of electronics industry. A number of interesting and difficult mathematical problems arise in the design phase (e.g., placement of components, wire routing, contact minimization) and in the manufacturing process of printed circuit boards. The authors report here about two of the latter problems: plotting masks and drilling holes. This paper is not meant to survey all mathematical techniques that are available and to show what can be achieved by a thorough and careful analysis of a practical problem and by developing sophisticated and special purpose algorithms. The authors simply want to show what could be achieved in an industrial setup with a prespecified tight frame for the code development and with quite low limits on the running times for the algorithms. The results were remarkable in the sense that relatively straightforward heuristics were able to improve the solutions used in practice by a substantial margin. In particular, the positioning head moves of the plotting and drilling machines could be reduced by about 10% to almost 90%. This led to reductions of the total production time by 5% to almost 35% and thus to a considerable increase of the production capacity of the machines on the average.