Publications
Detailed Information
On the Complexity of the Production-Transportation Problem
Cited 9 time in
Web of Science
Cited 14 time in Scopus
- Authors
- Issue Date
- 1996-02
- Citation
- SIAM J. Optim., 6 (1996), pp.250-264
- Keywords
- production-transportation problem ; concave minimization ; parametric linear programming ; Monge sequence
- Abstract
- 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.
- ISSN
- 1052-6234
- Language
- English
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.