On parallel machine replacement problems with general replacement cost functions and stochastic deterioration

Suzanne Childress, Pablo Durango-Cohen*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


The parallel machine replacement problem consists of finding a minimum cost replacement policy for a finite population of economically interdependent machines. In this paper, we formulate a stochastic version of the problem and analyze the structure of optimal policies under general classes of replacement cost functions. We prove that for problems with arbitrary cost functions, there can be optimal policies where a machine is replaced only if all machines in worse states are replaced (Worse Cluster Replacement Rule). We then show that, for problems with replacement cost functions exhibiting nonincreasing marginal costs, there are optimal policies such that, in any stage, machines in the same state are either all kept or all replaced (No-Splitting Rule). We also present an example that shows that economies of scale in replacement costs do not guarantee optimal policies that satisfy the No-Splitting Rule. These results lead to the fundamental insight that replacement decisions are driven by marginal costs, and not by economies of scale as suggested in the literature. Finally, we describe how the optimal policy structure, i.e., the No-Splitting and Worse Cluster Replacement Rules, can be used to reduce the computational effort required to obtain optimal replacement policies.

Original languageEnglish (US)
Pages (from-to)409-419
Number of pages11
JournalNaval Research Logistics
Issue number5
StatePublished - Aug 2005


  • Dynamic programming
  • Economic interactions
  • Equipment replacement
  • Markov decision processes

ASJC Scopus subject areas

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research


Dive into the research topics of 'On parallel machine replacement problems with general replacement cost functions and stochastic deterioration'. Together they form a unique fingerprint.

Cite this