S-Space College of Engineering/Engineering Practice School (공과대학/대학원) Dept. of Industrial Engineering (산업공학과) Journal Papers (저널논문_산업공학과)
On the Complexity of the Production-Transportation Problem
- Hochbaum, Dorit S.; Hong, Sung-Pil
- Issue Date
- SIAM J. Optim., 6 (1996), pp.250-264
- production-transportation problem; concave minimization; parametric linear programming; Monge sequence
- The production-transportation problem (PTP) is a generalization of the transportation problem. In PTP, we decide not only the level of shipment from each source to each sink but also the level of supply at each source. A concave production cost function is associated with the assignment of supplies to sources. Thus the objective function of PTP is the sum of the linear transportation costs and the production costs. We show that this problem is generally NP-hard and present some polynomial classes. In particular, we propose a polynomial algorithm for the case in which the transportation cost matrix has the Monge property and the number of sources is fixed. The algorithm generalizes a polynomial algorithm of Tuy, Dan, and Ghannadan [Open Res. Lett., 14 (1993), pp. 99-109] for the problem with two sources.
- Files in This Item: