A flow algorithm for network synchronization

• 成果类型: Article
• 署名作者: Hassin, R
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.44.4.570
• 发表日期: 1996
• 页码: 570-579
• 关键词: network flow algorithms; application to synchronization of node variables; production scheduling; synchronization of cyclic work stations; transportation traffic models; traffic signal synchronization

摘要

The problem we treat is defined on a graph where each node is associated with a variable and there are loss functions defined on the arcs, depending on the difference between the corresponding node variables. The objective is to compute values for the node variables so as to minimize the sum of losses. We exploit the relation between this problem and network flows optimization and use it in developing an approximation algorithm for the problem A main application of the problem is the synchronization of fixed cycle traffic signals.