Optimization of an SMD placement machine and flows in parametric networks

Title:

Optimization of an SMD placement machine and flows in parametric networks

Creator:

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

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:6df5c48c-3ef8-4f52-a184-1a401928cbfc
uuid:6df5c48c-3ef8-4f52-a184-1a401928cbfc

Subject:

SMD machine optimization, network flow, and algorithm

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

[722]-731

Source:

Kybernetika | 2011 Volume:47 | Number:5

Harvested from:

CDK

Metadata only:

false