SHERP

On the Complexity of the Production-Transportation Problem

Cited 0 time in webofscience Cited 0 time in scopus
Authors
Hochbaum, Dorit S.; Hong, Sung-Pil
Issue Date
1996-02
Publisher
Society for Industrial and Applied Mathematics
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
URI
http://hdl.handle.net/10371/5346
DOI
https://doi.org/10.1137/0806014
https://doi.org/10.1137/0806014
Files in This Item:
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse