Geodesic
Optimization of an SMD placement machine and flows in parametric networks
Kybernetika, Tome 47 (2011) no. 5, pp. 722-731 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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 $n$ vertices and $m$ arcs a set $F$ 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 $F$ 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 $O(|F|)$ different target values and so this approach leads to a strongly polynomial algorithm consisting of at most $O(|F|)$ maximum flow computations.
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 $n$ vertices and $m$ arcs a set $F$ 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 $F$ 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 $O(|F|)$ different target values and so this approach leads to a strongly polynomial algorithm consisting of at most $O(|F|)$ maximum flow computations.
Classification : 05C21, 90B30, 90C27
Keywords: SMD machine optimization; network flow; algorithm 
@article{KYB_2011_47_5_a4,
     author = {Cechl\'arov\'a, Katar{\'\i}na and Fleiner, Tam\'as},
     title = {Optimization of an {SMD} placement machine and flows in parametric networks},
     journal = {Kybernetika},
     pages = {722--731},
     year = {2011},
     volume = {47},
     number = {5},
     mrnumber = {2850459},
     zbl = {1236.90046},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2011_47_5_a4/}
}
TY  - JOUR
AU  - Cechlárová, Katarína
AU  - Fleiner, Tamás
TI  - Optimization of an SMD placement machine and flows in parametric networks
JO  - Kybernetika
PY  - 2011
SP  - 722
EP  - 731
VL  - 47
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/KYB_2011_47_5_a4/
LA  - en
ID  - KYB_2011_47_5_a4
ER  - 
%0 Journal Article
%A Cechlárová, Katarína
%A Fleiner, Tamás
%T Optimization of an SMD placement machine and flows in parametric networks
%J Kybernetika
%D 2011
%P 722-731
%V 47
%N 5
%U http://geodesic.mathdoc.fr/item/KYB_2011_47_5_a4/
%G en
%F KYB_2011_47_5_a4
Cechlárová, Katarína; Fleiner, Tamás. Optimization of an SMD placement machine and flows in parametric networks. Kybernetika, Tome 47 (2011) no. 5, pp. 722-731. http://geodesic.mathdoc.fr/item/KYB_2011_47_5_a4/

[1] Ahuja, R. H., Magnanti, T. L., Orlin, J. B.: Network flows, Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs 1993. | MR | Zbl

[2] Arai, T., Ueno, S., Kajitani, Y.: Generalization of a theorem on the parametric maximum flow problem. Discrete Appl. Math. 41 (1993), 69-74. | DOI | MR | Zbl

[3] Ayob, M., Kendall, G.: A survey of surface mount device placement machine optimisation: Machine classification. European J. Oper. Res. 186 (2008), 893-914. | DOI

[4] Carstensen, P. J.: Complexity of some parametric integer and network programming problems. Math. Programming 26 (1983), 64-75. | DOI | MR | Zbl

[5] Chen, Y. L.: A parametric maximum flow algorithm for bipartite graphs with applications. European J. Oper. Res. 80 (1995), 226-235. | DOI | Zbl

[6] Chung, S. J., Hamacher, H. W., Maffioli, F., Murty, K. G.: A note on combinatorial optimization problems with max-linear objective function. Discrete Appl. Math. 42 (1991), 139-145. | DOI | MR

[7] Duman, E., Or, I.: The quadratic assignment problem in the context of the printed circuit board assembly. Comput. Oper. Res. 34 (2007), 163-179. | DOI | Zbl

[8] Ford, L. R., Fulkerson, D. R.: Maximal flow through a network. Canad. J. Math. 8 (1956), 399-404. | DOI | MR | Zbl

[9] Foulds, L. R., Hamacher, H. W.: Optimal bin location and sequencing in printed circuit board assembly. European J. Oper. Res. 66 (1993), 279-290. | DOI | Zbl

[10] Gallo, G., Grigoriadis, M. D., Tarjan, R. E.: A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18 (1989), 30-55. | DOI | MR | Zbl

[11] Hamacher, H. W., Foulds, L. R.: Algorithms for flows with parametric capacities. ZOR - Methods and Models Oper. Res. 33 (1989), 21-37. | MR | Zbl

[12] Korte, B., Vygen, J.: Combinatorial Optimization, Theory and Algorithms. Springer, Berlin 2008. | MR | Zbl

[13] Scutella, M. G.: A note on the parametric maximum flow problem and some related reoptimization issues. Ann. Oper. Res. 150 (2007), 231-244. | DOI | MR | Zbl

[14] Zhang, B., Ward, J., Feng, Q.: A simultaneous parametric maximum-flow algorithm for finding the complete chain of solutions. Hewlet-Packard Development Company, Preprint, 2005.