A military maintenance planning and scheduling problem

In the maintenance workload problem (MWP), we must assign each of a set of items in need of repair to one facility of a set of repair facilities. We must also schedule the item repairs at each facility. While we would like to deliver all items on time and at minimum cost, some amount of tardiness may be unavoidable. Alternatively, we may wish to identify system solutions that allow some amount of total system tardiness in order to reduce total operating cost. The Army Materiel Systems Analysis Activity, performed the original work on the MWP, creating a restriction of the full problem to identify feasible solutions. We employ two alternate models to generate provably near-optimal solutions. The first is a different restriction of the full problem that generates good feasible solutions. The second is a Benders decomposition of the full-sized problem that generates a tight lower bound on the problem objective function even in cases where the full problem is prohibitively large (i.e. so large that it took prohibitively long to provide all of the data to the optimization). While we cannot generate solutions that are substantially less costly than those found with the existing model for the instances available, our method proves the near optimality of both prior solutions and those we generate. Of particular note is that our method, even employing the two models in series, is substantially faster than the original model for the largest instances of the MWP.