AN OPTIMAL MULTIMACHINE REPLACEMENT POLICY IN A SERIALLY DEPENDENT PRODUCTION SYSTEM

Here we 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, we 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 o f M fewer than currently employed by heuristic procedures on alternate formulations. Specialized monotone cost structures are no longer nece ssary, thus extending the class of problems which can be solved effici ently. Computations done using the reformulation's linear programming relaxation on randomly generated problems typically produced integer s olutions without branching, even in problems with 75 machines and 15 t ime periods. In situations where exact optimal solutions are required, the reformulation partially remedies the slow convergence witnessed i n earlier studies using branch and bound techniques.