This research addresses the equipment scheduling problem under disruptions in United States Postal Service mail processing and distribution centers. These facilities contain a large variety of equipment and employ a non-homogeneous workforce that work on shifts of various lengths and start times. The scheduling of equipment (the determination of the configuration and usage of equipment to match mail arrivals) and the scheduling of workforce (the determination of the optimal size and composition of the workforce, their days off / lunch assignments, and overtime usage) to meet processing service commitment with a constantly changing demand are some of the most challenging problems.
Over the years, there have been many research studies that focused on solution of the postal equipment and staff scheduling problems. A comprehensive review of these studies is conducted. In the most general sense, each of the equipment and staff schedule problems can be decomposed temporally so and hierarchical analytic approaches have been adopted. Along the time axis, these studies can be classified into strategic, tactical and operational levels.
This thesis focuses on the operational equipment scheduling problem or equipment scheduling under disruptions and addresses the adjustment of production plans and workforce schedules through the use of overtime and flexible employees in the face of disruptions such as demand fluctuation and absenteeism that happen on a daily basis and may significantly change demand and the size of workforce. This problem is modeled as a large-scale integer program, which contains equipment scheduling, shift scheduling and overtime management, and break assignment modules. Comprehensive experiments have been designed to investigate the effects of the use of overtime, the control of absenteeism, and the importance of integrating equipment and workforce scheduling simultaneously. The model integrates seamlessly with other research studies and provides the necessary tools to manage the resources in a facility on a routine basis.
To improve computational time, an efficient LP based decomposition algorithm has been developed. The algorithm uses linear programming solutions as target solutions to construct a local search process to examine neighboring integer solutions. The heuristic was first proposed for the equipment scheduling under disruptions and then extended to the staff scheduling problem where multiple diverse initial solutions were generated to cover the solution landscape. These heuristics were computational efficient and were able to quickly obtains high-quality feasible solutions and delivers final solutions on par with the state of the art branch and bound algorithm in the solution of integer programs.