A note (and a ‘further note’) on parallel machine replacement

Jones, Zydiak, and Hopp consider the parallel machine replacement problem (PMRP) in which there are both fixed and variable costs associated with replacing machines. Increasing maintenance cost motivates replacements, and a fixed replacement cost provides incentive for replacing machines of the same age in clusters. They prove two intuitive but important results for finite- or infinite-horizon PMRPs, which significantly reduce the size of the linear programming (LP) formulation of the problem and computing efforts required to obtain an optimal replacement policy. Their results are the no-splitting rule and the older cluster replacement rule. Under a slightly weaker set of assumptions, the authors prove a third rule, the all-or-none rule, which states that in any period, an optimal policy is to keep or to replace all the machines regardless of age. This result further reduces the size of the LP formulation of the PMRP.