Kybernetika 47 no. 5, 722-731, 2011

Optimization of an SMD placement machine and flows in parametric networks

Katarína Cechlárová and Tamás Fleiner

Abstract:

In the minimization of the number of subtours made by the insertion head of an SMD placement machine a variant of the network flow problem arose. In a network with <span class="tex">n</span> vertices and <span class="tex">m</span> arcs a set <span class="tex">F</span> of arcs (parametrized arcs) is given. The task is to find a flow of a given size such that the maximum of flow values along the arcs from <span class="tex">F</span> is minimized. This problem can be solved by a sequence of maximum flow computations in modified networks where the capacities of the parametrized arcs are successively set to an increasing sequence of target parameter values. We show that it suffices to consider at most <span class="tex">O(|F|)</span> different target values and so this approach leads to a strongly polynomial algorithm consisting of at most <span class="tex">O(|F|)</span> maximum flow computations.

Keywords:

algorithm, SMD machine optimization, network flow

Classification:

90B30, 90C27, 05C21

References:

  1. R. H. Ahuja, T. L. Magnanti and J. B. Orlin: Network flows, Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs 1993.   CrossRef
  2. T. Arai, S. Ueno and Y. Kajitani: Generalization of a theorem on the parametric maximum flow problem. Discrete Appl. Math. 41 (1993), 69-74.   CrossRef
  3. M. Ayob and G. Kendall: A survey of surface mount device placement machine optimisation: Machine classification. European J. Oper. Res. 186 (2008), 893-914.   CrossRef
  4. P. J. Carstensen: Complexity of some parametric integer and network programming problems. Math. Programming 26 (1983), 64-75.   CrossRef
  5. Y. L. Chen: A parametric maximum flow algorithm for bipartite graphs with applications. European J. Oper. Res. 80 (1995), 226-235.   CrossRef
  6. S. J. Chung, H. W. Hamacher, F. Maffioli and K. G. Murty: A note on combinatorial optimization problems with max-linear objective function. Discrete Appl. Math. 42 (1991), 139-145.   CrossRef
  7. E. Duman and I. Or: The quadratic assignment problem in the context of the printed circuit board assembly. Comput. Oper. Res. 34 (2007), 163-179.   CrossRef
  8. L. R. Ford and D. R. Fulkerson: Maximal flow through a network. Canad. J. Math. 8 (1956), 399-404.   CrossRef
  9. L. R. Foulds and H. W. Hamacher: Optimal bin location and sequencing in printed circuit board assembly. European J. Oper. Res. 66 (1993), 279-290.   CrossRef
  10. G. Gallo, M. D. Grigoriadis and R. E. Tarjan: A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18 (1989), 30-55.   CrossRef
  11. H. W Hamacher and L. R. Foulds: Algorithms for flows with parametric capacities. ZOR - Methods and Models Oper. Res. 33 (1989), 21-37.   CrossRef
  12. B. Korte and J. Vygen: Combinatorial Optimization, Theory and Algorithms. Springer, Berlin 2008.   CrossRef
  13. M. G. Scutella: A note on the parametric maximum flow problem and some related reoptimization issues. Ann. Oper. Res. 150 (2007), 231-244.   CrossRef
  14. B. Zhang, J. Ward and Q. Feng: A simultaneous parametric maximum-flow algorithm for finding the complete chain of solutions. Hewlet-Packard Development Company, Preprint, 2005.   CrossRef