A BRANCH‐AND‐BOUND APPROACH FOR SEQUENCING EXPANSION PROJECTS

Abstract

The paper examines the problem of finding a sequence of a finite set of expansion projects to meet a deterministic demand projection at minimum discounted cost. As the general problem is NP‐complete, we focus on the case when the demand growth is in the exponential form, which is quite often found in applications of electric power generation, transportation, water resources and communication. We find that projects' annual costs are an effective ranking criteria for determining an optimal expansion sequence. As the annual cost for a project is a function of time or capacity level, an optimal expansion sequence can be obtained easily if dominance orders of the annual costs exist for all pairwise projects, which is likely to be the case for most practical problems. When the annual costs for the projects are in conditional order, a branch‐and‐bound algorithm has been developed to effectively reduce the searching range. Our extensive computational results show that the approach is very efficient compared with the other approaches and always solves the problem to optimum although the optimality of the approach still remains to be proven.

Keywords

FACILITIES/EQUIPMENT PLANNING CAPACITY EXPANSION BRANCH AND BOUND SEQUENCING ANNUAL COST

Get full access to this article

View all access options for this article.

References

Akileswaran

Hazen

G. B.

, and Morin

T. L.

(1983), “Complexity of the Project Sequencing Problem,” Operations Research, 31, 4, 772–778.

Baker

K. R.

and Schrage

L. E.

(1978), “Finding an Optimal Sequence by Dynamic Programming: An Extension to Precedence‐Related Tasks,” Operations Research, 26, 1, 111–120.

Butcher

W. S.

Haimes

Y. Y.

, and Hall

W. A.

(1969), “Dynamic Programming for the Optimal Sequencing of Water‐Supply Projects,” Water Resources Research, 5, 1196–1204.

Cohen

M. A.

and Halperin

R. M.

(1986), “Optimal Technology Choice in a Dynamic‐Stochastic Environment,” Journal of Operations Management, 6, 3, 317–331.

Dale

K. M.

(1966), “Dynamic Programming Approach to the Selection and Timing of Generation Plant Additions,” Proceedings of the Institute of Electrical Engineering, 113, 803–811.

Dutta

and Lim

J. L.

(1992), “A Multi‐period Capacity Planning Model For Backbone Computer Communication Networks,” Operations Research, 40, 4, 689–705.

Erlenkotter

(1973), “Sequencing Expansion Projects,” Operations Research, 21, 3, 542–553.

Erlenkotter

(1989), “Average Cost Expansion Sequencing,” Operations Research tetter, 8, 4, 185–187.

Erlenkotter

and Rogers

J. S.

(1977), “Sequencing Competitive Expansion Projects,” Operations Research, 25, 6, 937–951.

10.

Fine

C. H.

and Freund

R. M.

(1990), “Optimal Investment in Product‐Flexible Manufacturing Capacity,” Management Science, 36, 4, 449–466.

11.

Freidenfelds

(1981), Capacity Expansion, Elsevier North Holland Inc., New York.

12.

Gupta

Buzacott

J. A.

Gerchak

AND Y.

(1988), Economic Analysis of Investment Decisions in Flexible Manufacturing Systems, Working Paper, Department of Management Science, University of Waterloo, Waterloo, Ontario, Canada.

13.

Held

, and Karp

R. M.

(1962), “A Dynamic Programming Approach to Sequencing Problems,” SIAM Journal Applied Mathematics, 10, 196–210.

14.

Jack

Kai

, and Shulman

(1992), “Design and Implementation of an Interactive Optimization System for Telephone Network Planning,” Operations Research, 40, 1, 14–25.

15.

and Tirupati

(1992), “Technology Selection and Capacity Planning for Manufacturing Systems” in Intelligent Design and Manufacturing, pp. 257–288, Andrew

Kusiak

(ed.), John Wiley & Sons, Inc., New York.

16.

(1994), “Dynamic Capacity Expansion Problem with Multiple Product Families: Technology Selection and Timing of Capacity Additions,” Operations Research, 42, 5, 958–976.

17.

Luss

(1982), “Operations Research and Capacity Expansion Problems: A Survey,” Operations Research, 30, 5, 907–947.

18.

Mitten

L. G.

and Tsou

C. A.

(1973), “Efficient Solution Procedures for Certain Scheduling and Sequencing Problems” in Sympossium on the Theory of Scheduling and its Applications, Elmaghraby

(ed.), Springer‐Verlag, Berlin, 127–142.

19.

Neebe

A. W.

and Rao

M. R.

(1986), “Sequencing Capacity Expansion Projects in Continuous Time,” Man agement Science, 32, 11, 1467–1479.

20.

Neebe

A. W.

(1983), “The Discrete‐time Sequencing and Expansion Problem,” Operations Research, 31, 3, 546–558.

21.

O'laoghaire

D. T.

and Himmelblau

D. M.

(1971), “Optimal Capital Investment in the Expansion of an Existing Water Resources System,” Water Resources Bulletin, 7, 1194–1209.

22.

O'laoghaire

D. T.

(1972), “Modeling and Sensitivity Analysis for Planning Decisions in Water Resources Expansion,” Water Resources Bulletin, 8, 653–668.

23.

O'laoghaire

D. T.

(1974), Optimal Expansion of a Water Resources System, Academic Press, New York.

24.

Sahinidis

N. V.

and Grossmann

I. E.

(1992), “Reformulation of the Multi‐period MILP Model for Capacity Expansion of Chemical Processes,” Operations Research, 40, Suppl. 1, S127–S144.

25.

Sahinidis

N. V.

Grossmann

I. E.

Fornari

, and Chathrathi

(1989), “Long Range Planning Model for the Chemical Process Industries,” Computers and Chemical Engineering, 13, 1049–1063.

26.

Shimizu

and Takamatsu

(1985), “Application of Mixed‐Integer Linear Programming in Multi‐Term Expansion Planning Under Multiobjectives,” Computers and Chemical Engineering, 9, 367–378.

27.

Stanton

and While

(1986), Constructive Combinatorics, Springer‐Verlag, New York.