Model and solution techniques for machine scheduling problems in high volume factories

The USPS is the second largest employer in the U.S. with over 800,000 personnel. More than 1/3 of them work at approximately 275 mail processing centers (P&DCs) nationwide. These facilities run 24 hours a day, 7 days a week and contain a wide variety of equipment for accepting, processing and transporting the mail. This dissertation focuses on developing a comprehensive framework on how to manage the use of this equipment with minimum labor cost. The equipment scheduling problem is modeled as a large-scale mixed-integer program with multi-criteria. One of the main contributions in the model is the inclusion of a surrogate for labor costs in the form of worker shifts that match daily operations. The problem is solved sequentially using a three-phase methodology related to goal programming in conjunction with a post-processor to assign operations to machines. Two specialized algorithms have been investigated to solve the mixed-integer program in the third phase. The first is a piece-by-piece LP-based heuristic and the second is a Benders decomposition. The heuristic uses the LP fractional solution as a target and attempts to find integer solutions that are as close to it as possible. The process consists of solving the LP relaxation and two additional integer programs and is similar to a piece-by-piece decomposition used in nonlinear programming. While a branch and bound algorithm is computationally expensive and the classic Benders algorithm failed to give feasible solutions, the LP-based heuristic yields near-optimal almost feasible solutions orders of magnitude faster. In post-processing, a multi-period machine assignment problem is solved. This problem is modeled as a bi-criterion, 0-1 integer program and a two-stage heuristic is developed. In a comparative study, high quality solutions were routinely provided by the heuristic in negligible time when compared to a branch and bound algorithm. For most hard problem instances, the branch-and-bound algorithm was not able to even find continuous solutions within acceptable time limits. The methodology developed in this dissertation is demonstrated with data provided by the Dallas P&DC. The results indicate that annual savings on the order of $1.6 million per facility can be achieved. The system will be implemented nationwide in the next three years.