An Efficient Algorithm for the Multiperiod Capacity Expansion of One Location in Telecommunications

Iraj Saniee
Additional contact information
Iraj Saniee: Bell Communications Research, Morristown, New Jersey

Operations Research, 1995, vol. 43, issue 1, 187-190

Abstract: The minimum cost multiperiod capacity expansion of one location in telecommunications network planning can be formulated as a time-dependent knapsack problem. The problem consists of meeting integral demands at distinct time periods at minimum total discounted cost through a selection of items (with integral costs and capacities) from a collection of N distinct types of objects. This note presents an efficient pseudopolynomial time solution to this time-dependent knapsack problem. The technique involves an initial dynamic programming run with time complexity O(N(D + C)) followed by a shortest path algorithm with worst-case time complexity O(C 2T ) through a suitably defined network, where D and C are the maxima of the values of the demands and capacities, and T is the number of time periods to be considered. The application of this technique to the problem of optimal capacity expansion of one location in telecommunications network planning is described and computational results are reported.

Keywords: dynamic programming; deterministic: solution to time-dependent knapsack problems; facilities/equipment planning; capacity expansion: exact solution via shortest paths (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.43.1.187 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:43:y:1995:i:1:p:187-190

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().