A Lagrangian Relaxation Based Approach to Schedule Asset Overhaul and Repair Services (2005)

Overhaul and repair services are important segments of the remanufacturing industry, and are characterized by complicated disassembly, repair and assembly process plans, stochastic operations, and the usage of rotable inventory. In view of today's time-based competition, effectively scheduling such services and managing rotable inventory and uncertainties are becoming imperative to achieve on-time deliveries and low overall costs. In this paper, a novel formulation for overhaul and repair services is presented where key characteristics, such as uncertain asset arrivals and operation processing times, and rotable parts are abstracted to model an overhaul center and multiple repair shops in a distributed framework to reflect organizational structures. Interactions between the overhaul center and repair shops are described by sets of coupling constraints across the organizations. Rotable inventory dynamics is formulated in terms of repair operation completion times and asset assembly beginning times to facilitate minimization of inventory holding costs through scheduling. A solution methodology combining Lagrangian relaxation, stochastic dynamic programming, and heuristics is developed to schedule operations in a coordinated manner to minimize total tardiness, earliness, and inventory holding costs. Additionally, penalty terms associated with coupling constraint violations are introduced to the objective function to improve algorithm convergence and schedule quality, and a surrogate optimization framework is used to overcome the inseparability difficulty caused by the penalty terms. Numerical testing results show that the new approach is computationally effective to handle rotable inventory and uncertainties, and provides high quality schedules with low overall costs for stochastic remanufacturing systems. Note to Practitioners-Overhaul and repair services for jet engines, helicopters, airplanes, are important segments of the remanufacturing industry, and are characterized by complicated disassembly, repair and assembly process plans, stochastic operations, and the usage of rotable inventory. In view of today's highly competitive business climate, effectively scheduling such services and managing rotable inventory and uncertainties are becoming critical to achieve on-time deliveries and low overall costs. In this paper, a novel formulation for overhaul and repair services is presented where key characteristics, such as uncertain asset arrivals and operation processing times, and rotable parts are abstracted to model an overhaul center and multiple repair shops in a distributed framework to reflect organizational structures. A solution methodology based on decomposition and coordination is developed to schedule operations to minimize total tardiness, earliness, and inventory holding costs. Numerical testing results show that the method is computationally efficient for managing rotable inventory and uncertainties, and generates high quality schedules with low overall costs. The value of rotable inventory to reduce tardiness costs and buffer uncertainties is demonstrated, and the robustness of the new method is evaluated by cases with different settings of machine utilization levels and uncertainty levels. The scalability of the method to solve large problems with hundreds of assets is also demonstrated.