Here the authors investigate the serially dependent, multi-machine replacement problem. Given a planning horizon with T periods, M machines of T+1 possible vintages, costs for machine operations, machine replacements, and shutdown times, they investigate a linear programming reformulation which involves half the variables and a factor of T fewer constraints than earlier forms. Only T binary variables are necessary, a factor of M fewer than currently employed by heuristic procedures on alternate formulations. Specialized monotone cost structures are no longer necessary, thus extending the class of problems which can be solved efficiently. Computations done using the reformulation’s linear programming relaxation on randomly generated problems typically produced integer solutions without branching, even in problems with 75 machines and 15 time periods. In situations where exact optimal solutions are required, the reformulation partially remedies the slow convergence witnessed in earlier studies using branch and bound techniques.
