Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
SMD machine optimization; network flow; algorithm
SMD machine optimization; network flow; algorithm
Summary:
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.
References:
[1] Ahuja, R. H., Magnanti, T. L., Orlin, J. B.: Network flows, Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs 1993. MR 1205775 | Zbl 1201.90001
[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 10.1016/0166-218X(93)90245-J | MR 1197251 | Zbl 0780.90029
[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 10.1016/j.ejor.2007.03.042
[4] Carstensen, P. J.: Complexity of some parametric integer and network programming problems. Math. Programming 26 (1983), 64-75. DOI 10.1007/BF02591893 | MR 0696727 | Zbl 0585.90065
[5] Chen, Y. L.: A parametric maximum flow algorithm for bipartite graphs with applications. European J. Oper. Res. 80 (1995), 226-235. DOI 10.1016/0377-2217(93)E0161-P | Zbl 0928.90006
[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 10.1016/0166-218X(93)90043-N | MR 1217094
[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 10.1016/j.cor.2005.05.004 | Zbl 1113.90130
[8] Ford, L. R., Fulkerson, D. R.: Maximal flow through a network. Canad. J. Math. 8 (1956), 399-404. DOI 10.4153/CJM-1956-045-5 | MR 0079251 | Zbl 0073.40203
[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 10.1016/0377-2217(93)90217-B | Zbl 0771.90060
[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 10.1137/0218003 | MR 0978165 | Zbl 0679.68080
[11] Hamacher, H. W., Foulds, L. R.: Algorithms for flows with parametric capacities. ZOR - Methods and Models Oper. Res. 33 (1989), 21-37. MR 0988396 | Zbl 0669.90042
[12] Korte, B., Vygen, J.: Combinatorial Optimization, Theory and Algorithms. Springer, Berlin 2008. MR 2369759 | Zbl 1207.90002
[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 10.1007/s10479-006-0155-z | MR 2304139 | Zbl 1144.90504
[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.
Search
Partner of
