A Min Cost Flow Solution for Dynamic Assignment Problems in Networks with Storage Devices
提出一种最小费用流方法，解决带存储设备网络中的动态分配问题，通过构建分层超图将问题转化为标准网络流问题，适用于需要优化流量分配和存储决策的场景。
The paper presents a minimum-cost flow approach for dynamic assignment procedures for networks with storage devices over time. Decision variables are diversion of flow at specific nodes and the storage of material in buffers which have to meet upper and lower capacity constraints. Evaluation of a decision is based on utility functions which are assumed to be piecewise linear and concave. The solution is based on a transformation into a network flow problem as suggested by Kuczera (1989). The temporal dimension of the problem is handled by constructing a supergraph with a layer for each time period. These layers are connected by temporal arcs. Thus the problem can be solved entirely by well-known algorithms for the minimum-cost flow problem which yield the optimal solution and determine automatically whether a feasible solution exists or not. The complexity of the proposed algorithm is pseudopolynomial, i.e., linear in the size of the network (measured by nodes, arcs, and buffers), linear in the amount of inflow, and quadratic in the number of time periods under consideration.