Kybernetika - Article detailKybernetikaInternational journal of Institute of Information Theory and AutomationOptimization of an SMD placement machine and flows in parametric networksn 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.]]>R. H. AhujaT. L. MagnantiJ. B. OrlinNetwork flows, Theory, Algorithms and Applications.Prentice Hall, Englewood Cliffs 1993.T. AraiS. UenoY. KajitaniGeneralization of a theorem on the parametric maximum flow problem.Discrete Appl. Math. 41 (1993), 69-74.M. AyobG. KendallA survey of surface mount device placement machine optimisation: Machine classification.European J. Oper. Res. 186 (2008), 893-914.P. J. CarstensenComplexity of some parametric integer and network programming problems.Math. Programming 26 (1983), 64-75.Y. L. ChenA parametric maximum flow algorithm for bipartite graphs with applications.European J. Oper. Res. 80 (1995), 226-235.S. J. ChungH. W. HamacherF. MaffioliK. G. MurtyA note on combinatorial optimization problems with max-linear objective function.Discrete Appl. Math. 42 (1991), 139-145.E. DumanI. OrThe quadratic assignment problem in the context of the printed circuit board assembly.Comput. Oper. Res. 34 (2007), 163-179.L. R. FordD. R. FulkersonMaximal flow through a network.Canad. J. Math. 8 (1956), 399-404.L. R. FouldsH. W. HamacherOptimal bin location and sequencing in printed circuit board assembly.European J. Oper. Res. 66 (1993), 279-290.G. GalloM. D. GrigoriadisR. E. TarjanA fast parametric maximum flow algorithm and applications.SIAM J. Comput. 18 (1989), 30-55.H. W HamacherL. R. FouldsAlgorithms for flows with parametric capacities.ZOR - Methods and Models Oper. Res. 33 (1989), 21-37.B. KorteJ. VygenCombinatorial Optimization, Theory and Algorithms.Springer, Berlin 2008.M. G. ScutellaA note on the parametric maximum flow problem and some related reoptimization issues.Ann. Oper. Res. 150 (2007), 231-244.B. ZhangJ. WardQ. FengA simultaneous parametric maximum-flow algorithm for finding the complete chain of solutions.Hewlet-Packard Development Company, Preprint, 2005.