Selected topics on integrated production-scheduling and maintenance-planning problems

Abstract

This thesis is focused on the integrated production-scheduling and maintenance-planning problem with random failures. Production jobs need to be scheduled on one or several machine(s) while the processing of them depletes the machine's condition. With worsening condition, the machine is more likely to fail randomly and hence causing delays in the production. To reduce the possibility of failures, preventive maintenance activities can be scheduled throughout the production. These activities cause delays on their own. Hence, the random delays through failure and the planned delays through preventive maintenance must be balanced. This combined with the interrelations between production and the maintenance decision to fulfill a production-specific objective is the focus of this problem. The formulation used and the underlying assumptions are common in the literature. Given these assumptions, the problem is non-linear in character and little mathematical programming is used in the literature. Different approaches to this problem are proposed in this thesis. Mainly, mathematical programming and decomposition techniques are used to fill the revealed gaps.

For the single-machine version of the problem, two approaches are proposed. First, a branch-and-price algorithm is developed to solve the problem with expected-makespan objective. Different strategies to accelerate this algorithm are discussed and compared to the monolithic formulation of this problem. All show superior solving capabilities and outperform the monolithic approach clearly. Second, a branch-and-bound algorithm is proposed for the objective to minimize the total weighted expected completion time. Besides a mixed-integer program that can only solve small instances, this approach enhances a proposed branch-and-bound algorithm from the literature. An additional sequencing priority rule and problem-specific properties of the problem enables the solution of larger instances. Both can be utilized by the use of a general precedence formulation which is different to the mainly used rank-based formulation.

For the parallel-machine version of the problem, a decomposition approach is proposed decomposing the problem multiple times by use of a Benders' and a Dantzig-Wolfe decomposition. Through this approach the non-linearity is shifted to the subproblems and becomes more manageable. In addition to the used combinatorial cuts, also classical Benders' are derived from the good root relaxation of the Dantzig-Wolfe approach. Different configurations of the decomposition, the used cuts and their sequence of integration are compared with the monolithic model. All outperform this formulation. Further, the additional Dantzig-Wolfe decomposition and the classical Benders' cuts show an increase in performance.

For the flowshop version of the problem, a stochastic programming problem and an expected-value problem are proposed. A decomposition heuristic is developed for the stochastic programming. It uses problem-specific properties as lower bounds and decomposes the monolithic formulation in three problems. One for the sequencing decisions, one for the maintenance decision and a simulation to evaluate both decisions. The composed computational study focuses on the reduction of feasible solutions through the used lower bounds. For the expected-value version of the problem, an alternative mixed-integer formulation is proposed. A constraint-based formulation is developed to linearize the problem which is different to the binary mapping used in the previous works of this thesis. This can be also used in an iterative cutting approach. This formulation is compared to a binary mapping as well as a meta-heuristic approach and shows good performance.

All proposed approaches discussed in this thesis highlight the usability of mathematical programming and decomposition techniques for the given problem.

Im Rahmen dieser Arbeit wird das integrierte Produktionsplanungs- und Instandhaltungsplanungsproblem mit zufälligen Ausfällen behandelt. Produktionsaufträge müssen auf einer oder mehreren Maschinen eingeplant werden, während ihre Bearbeitung den Maschinenzustand verschlechtert. Je schlechter der Zustand der Maschine wird, desto wahrscheinlicher ist ein zufälliger Ausfall, der zu Verzögerungen in der Produktion führt. Um die Wahrscheinlichkeit von Ausfällen zu verringern, können während der gesamten Produktion vorbeugende Instandhaltungsaktivitäten eingeplant werden. Diese Aktivitäten verursachen ebenfalls Verzögerungen. Daher müssen die zufälligen Verzögerungen durch Ausfälle und die geplanten Verzögerungen durch vorbeugende Instandhaltungen abgewogen werden. Dies in Verbindung mit den Wechselbeziehungen zwischen der Produktions- und der Instandhaltungsentscheidung zur Erfüllung eines produktionsspezifischen Ziels steht im Mittelpunkt dieses Problems. Die verwendete Formulierung und die zugrunde liegenden Annahmen sind in der Literatur üblich. Angesichts dieser Annahmen ist das Problem nicht-linear, und in der Literatur wird selten mathematische Programmierung zur Lösung verwendet. In dieser Arbeit werden verschiedene Ansätze für das Problem vorgeschlagen. Hauptsächlich werden mathematische Programmierung und Dekompositionstechniken verwendet, um die aufgezeigten Lücken zu füllen.

Für die Ein-Maschinen-Version des Problems werden zwei Ansätze vorgeschlagen. Zunächst wird ein Branch-and-Price-Algorithmus dargestellt, um das Problem mit der Zielfunktion der erwarteten Zykluszeit zu lösen. Es werden verschiedene Strategien zur Beschleunigung dieses Algorithmus diskutiert und mit der monolithischen Formulierung des Problems verglichen. Alle zeigen eine überlegene Lösungsfähigkeit und übertreffen den monolithischen Ansatz deutlich. Zweitens wird ein Branch-and-Bound-Algorithmus zur Minimierung der Summe aller gewichteten erwarteten Fertigstellungszeiten vorgeschlagen. Neben einem gemischt-ganzzahligen Programm, das lediglich kleine Instanzen lösen kann, verbessert dieser Ansatz den in der Literatur vorgeschlagenen Branch-and-Bound-Algorithmus. Eine zusätzliche Prioritätsregel für die Reihenfolge und problemspezifische Eigenschaften des Problems ermöglichen die Lösung von größeren Instanzen. Beides kann durch die Verwendung einer allgemeinen Vorrangformulierung genutzt werden, die sich von der hauptsächlich verwendeten rang-basierten Formulierung unterscheidet.

Für die Parallelmaschinenversion des Problems wird ein Dekompositionsansatz vorgeschlagen, bei dem das Problem mit Hilfe einer Benders' und einer Dantzig-Wolfe-Dekomposition mehrfach zerlegt wird. Durch diesen Ansatz wird die Nichtlinearität auf die Teilprobleme verlagert und somit besser handhabbar. Zusätzlich zu den verwendeten kombinatorischen Schnitten werden auch klassische Benders' Schnitte aus der guten Relaxation des Dantzig-Wolfe-Ansatzes abgeleitet. Verschiedene Konfigurationen der Dekomposition, der verwendeten Schnitte und deren Integrationsreihenfolge werden mit dem monolithischen Modell verglichen. Alle schneiden besser ab als diese Formulierung und die zusätzliche Dantzig-Wolfe-Zerlegung sowie die klassischen Benders-Schnitte zeigen eine Leistungssteigerung.

Für die Flowshop-Version des Problems werden ein Ansatz für die stochastischen Programmierung und einer für das Erwartungswertproblem dargestellt. Für die stochastische Programmierung wird eine Dekompositionsheuristik entwickelt. Sie verwendet problemspezifische Eigenschaften als untere Schranken und zerlegt das Problem in ein Problem für die Reihenfolgeentscheidung, eines für die Instandhaltungsentscheidung und ein Simulationsmodell zur Bewertung beider Entscheidungen. Die zusammengestellte Rechenstudie zeigt die Reduktion der zulässigen Lösungen durch die verwendeten unteren Schranken. Für das Erwartungswertproblem wird eine alternative gemischt-ganzzahlige Formulierung vorgeschlagen. Zur Linearisierung des Problems wird eine nebenbedingungs-basierte Formulierung verwendet. Diese unterscheidet sich von dem Binary Mapping Ansatz, welcher zum Teil in den früheren Artikeln dieser Arbeit genutzt wurde. Die vorgeschlagene Formulierung kann auch in einem iterativen Ansatz zur Schnittgenerierung verwendet werden. Diese Formulierung wird sowohl mit dem Binary Mapping als auch mit einem meta-heuristischen Ansatz verglichen und zeigt eine gute Leistung.

Alle vorgeschlagenen Ansätze in dieser Arbeit unterstreichen die Anwendbarkeit der mathematischen Programmierung und der Dekompositionstechniken für das gegebene Problem.