Premium
Solution algorithms for the parallel replacement problem under economy of scale
Author(s) -
Chen ZhiLong
Publication year - 1998
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199804)45:3<279::aid-nav3>3.0.co;2-4
Subject(s) - time horizon , mathematical optimization , computer science , simple (philosophy) , scale (ratio) , horizon , integer (computer science) , shortest path problem , algorithm , mathematics , theoretical computer science , graph , epistemology , quantum mechanics , programming language , philosophy , physics , geometry
We consider the parallel replacement problem in which machine investment costs exhibit economy of scale which is modeled through associating both fixed and variable costs with machine investment costs. Both finite‐ and infinite‐horizon cases are investigated. Under the three assumptions made in the literature on the problem parameters, we show that the finite‐horizon problem with time‐varying parameters is equivalent to a shortest path problem and hence can be solved very efficiently, and give a very simple and fast algorithm for the infinite‐horizon problem with time‐invariant parameters. For the general finite‐horizon problem without any assumption on the problem parameters, we formulate it as a zero‐one integer program and propose an algorithm for solving it exactly based on Benders' decomposition. Computational results show that this solution algorithm is efficient, i.e., it is capable of solving large scale problems within a reasonable cpu time, and robust, i.e., the number of iterations needed to solve a problem does not increase quickly with the problem size. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 279–295, 1998