Planning and Scheduling Facility Workloa

This research considers a military maintenance planning and scheduling problem posed by the Army Materiel Systems Analysis Activity (AMSAA). The problem requires that we assign each of a large set of military equipment items to one of a number of possible maintenance facilities and schedule repairs for those items at each facility. Each item originates at a particular location and must arrive at a certain destination; transportation costs are incurred for moving the equipment items from origin to repair facility and from repair facility to destination. In general, we would like to achieve a minimal cost for operating this system. However, we would also like to understand how varying system total allowed tardiness affects total operating cost. Ideally, we would like to have some knowledge of the efficient frontier, so that decision makers can make well-informed decisions concerning the trade-off between cost and tardiness (readiness).;AMSAA constructed an integer program, which they call the "Sliding Windows Formulation" (SWF), to assign and schedule item repairs. In order to visualize the efficient frontier, they employ an objective function that is a scalar weighted combination of cost and tardiness. The weights can be varied and the model resolved to obtain different solutions. In order to achieve feasible solutions, the developer of the SWF system groups similar items into a batch represented by a single variable and limit the amount of exploration that the solver may perform (limiting the size of the branch and bound tree). Despite these restrictions, large instances still require runtimes in excess of sixteen hours. For these instances, sliding windows formulation is solved in six-month segments and assembled into a single solution, which (Kotkin et.al. 2011) identifies as the "Rolling Horizon" heuristic.;We opt to model the multi-objective aspect of the this problem by minimizing cost and constraining system total tardiness. Initially, we construct and compare three models: a model in standard formulation and two models based on different decomposition methods. One decomposed model is based on Bender's Decomposition, an approach that has been used by (Hooker 2007) to solve the Planning and Scheduling Problem (PSP), a problem similar to our problem of interest. We also construct a model based on extensive reformulation and column generation using Dantzig-Wolfe decomposition. While each of these approaches has certain merits, we find neither entirely satisfactory. Therefore, we consider the use of variable restriction to obtain good feasible solutions. The success of this approach in obtaining upper bounds quickly led us to outline two alternative methods: one approach uses the upper bound obtained from a variable restricted model with a lower bound obtained from a Benders Decomposition Formulation. Alternatively, we also use an approach known as sifting to obtain a strong lower bound and use the resulting variables to find an upper bound on the problem. We demonstrate substantially reduced optimization times for the largest instances of the MWP. We also demonstrate the use of our improved solution methods as means to identify and visualize the efficient frontier that trades off cost for tardiness.