| Title:
|
Optimization of an SMD placement machine and flows in parametric networks (English) |
| Author:
|
Cechlárová, Katarína |
| Author:
|
Fleiner, Tamás |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
47 |
| Issue:
|
5 |
| Year:
|
2011 |
| Pages:
|
722-731 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
SMD machine optimization |
| Keyword:
|
network flow |
| Keyword:
|
algorithm |
| MSC:
|
05C21 |
| MSC:
|
90B30 |
| MSC:
|
90C27 |
| idZBL:
|
Zbl 1236.90046 |
| idMR:
|
MR2850459 |
| . |
| Date available:
|
2011-11-10T15:38:59Z |
| Last updated:
|
2013-09-22 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/141687 |
| . |
| Reference:
|
[1] Ahuja, R. H., Magnanti, T. L., Orlin, J. B.: Network flows, Theory, Algorithms and Applications..Prentice Hall, Englewood Cliffs 1993. Zbl 1201.90001, MR 1205775 |
| Reference:
|
[2] Arai, T., Ueno, S., Kajitani, Y.: Generalization of a theorem on the parametric maximum flow problem..Discrete Appl. Math. 41 (1993), 69-74. Zbl 0780.90029, MR 1197251, 10.1016/0166-218X(93)90245-J |
| Reference:
|
[3] Ayob, M., Kendall, G.: A survey of surface mount device placement machine optimisation: Machine classification..European J. Oper. Res. 186 (2008), 893-914. 10.1016/j.ejor.2007.03.042 |
| Reference:
|
[4] Carstensen, P. J.: Complexity of some parametric integer and network programming problems..Math. Programming 26 (1983), 64-75. Zbl 0585.90065, MR 0696727, 10.1007/BF02591893 |
| Reference:
|
[5] Chen, Y. L.: A parametric maximum flow algorithm for bipartite graphs with applications..European J. Oper. Res. 80 (1995), 226-235. Zbl 0928.90006, 10.1016/0377-2217(93)E0161-P |
| Reference:
|
[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. MR 1217094, 10.1016/0166-218X(93)90043-N |
| Reference:
|
[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. Zbl 1113.90130, 10.1016/j.cor.2005.05.004 |
| Reference:
|
[8] Ford, L. R., Fulkerson, D. R.: Maximal flow through a network..Canad. J. Math. 8 (1956), 399-404. Zbl 0073.40203, MR 0079251, 10.4153/CJM-1956-045-5 |
| Reference:
|
[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. Zbl 0771.90060, 10.1016/0377-2217(93)90217-B |
| Reference:
|
[10] Gallo, G., Grigoriadis, M. D., Tarjan, R. E.: A fast parametric maximum flow algorithm and applications..SIAM J. Comput. 18 (1989), 30-55. Zbl 0679.68080, MR 0978165, 10.1137/0218003 |
| Reference:
|
[11] Hamacher, H. W., Foulds, L. R.: Algorithms for flows with parametric capacities..ZOR - Methods and Models Oper. Res. 33 (1989), 21-37. Zbl 0669.90042, MR 0988396 |
| Reference:
|
[12] Korte, B., Vygen, J.: Combinatorial Optimization, Theory and Algorithms..Springer, Berlin 2008. Zbl 1207.90002, MR 2369759 |
| Reference:
|
[13] Scutella, M. G.: A note on the parametric maximum flow problem and some related reoptimization issues..Ann. Oper. Res. 150 (2007), 231-244. Zbl 1144.90504, MR 2304139, 10.1007/s10479-006-0155-z |
| Reference:
|
[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. |
| . |
