Dantzig-Wolfe Decomposition and Lagrangean Relaxation-Based Heuristics for an Integrated Production and Maintenance Planning with Time Windows

I. Introduction

Maintenance is a task closely related to production scheduling in industrial settings. It is the operations or techniques that allow maintaining or restoring equipment to a specific state and guaranteeing a given service. Both activities conflict since, as it is known, maintenance is generally a secondary process in companies that have production as their core business. Indeed, production management often views maintenance in the context of hours or days out of service and fails to realize the strategic importance of incorporating maintenance in the manufacturing planning. On the other hand, management for the maintenance function attempts to impose constraints on production that it deems necessary to achieve complete equipment reliability. As we can see, the production planning and maintenance are dealt separately in the literature and also in the industry. Therefore, maintenance planning should be an integral part of the overall business strategy and should be coordinated and scheduled with manufacturing activities. So, we should consider maintenance as integral parts of the production plan rather than as interruptions to that plan. Any violation of the maintenance schedule is treated as a violation of the production plan integrity.

As a remedy to this problem, we develop an integrated model of production and maintenance planning at the tactical level. In the core of production planning, we find the single stage multi item capacitated lot sizing problem with demand shortages in which the schedules and lot sizes are planned for the production of multiple items that share capacity constrained resource. We deal with problems with tight capacities, and when we are in lack of capacity to produce the total demand, we try to spread the capacity among the items by minimizing the total amount of demand shortages. Maintenance planning problem is to determine the dates of preventive maintenance in time windows according to reliability of production equipment. When preventive maintenance actions are carried out the production line is restored to an ‘as-good-as-new (AGAN)’ status, and when a production line fails, a minimal repair is performed to restore it to an ‘as-bad-as-old (ABAO)’ status. The resulting problem is modelled as a linear mixed-integer program to minimize production, inventory, setup, demand shortage, preventive and corrective maintenance costs.

We develop two approaches to solve the integrated production planning and maintenance problem. The first heuristic is based on Dantzig-Wolfe decomposition (Dantzig and wolfe, 1960). The Dantzig-Wolfe Decomposition principle reformulates the original model. Column generation is then used to deal with the huge number of variables of the reformulated model. Finally, we apply a simple rounding heuristic and smoothing procedure in order to obtain integer solutions. The second heuristic is based on Lagrangean relaxation (Ficher, 1981) of the capacity constraints and sub-gradient optimization. At every step of sub-gradient method, feasibility and improvement procedures are applied to the solution of the Lagrangean problem.