Solution techniques for the blocking job shop scheduling problem with total tardiness minimization

Abstract

Planning the course of events and activities constitutes an everyday challenge in many companies. Complex decisions are to be made regarding the allocation of a diverse range of resources and the corresponding processing sequences of tasks. Especially in the manufacturing of highly customized goods and the operation of cost-intensive logistics systems, efficient schedules have an enormous effect on the long-term success of an enterprise. Therefore, the ambitious idea of a reliable decision support for human planners is pursued by researchers in scheduling theory for many decades. While several classical scheduling problems are well studied, the integration of real-world constraints and objectives shows a lack of theoretical understanding. In order to provide a profound study in this research direction, a practically relevant class of job shop scheduling problems is comprehensively investigated with regard to the boundaries of exact solvability by mixed-integer programming techniques, the applicability of well-known heuristic methods and the advantageousness of hybrid matheuristic approaches. The job shop scheduling problem is known as a combinatorial optimization problem of considerable intricacy, for which even simple variants are proven to be strongly NP-hard. A set of jobs is required to be handled by a set of machines, where every job features an individual technological route of processing. A single processing step of a job is denoted as an operation, which is defined by a designated machine and processing time. In order to implement real-world conditions, a release date is given for every job and the recirculation of jobs is allowed. The absence of intermediate buffers in the planning situation is considered as a special circumstance, for instance, occurring in the production of huge items, in robotic storage frameworks and in railbound logistics systems. A schedule is to be determined, which assigns certain periods of working time of the required machines to the operations of each job, so that the given restrictions are met. Motivated by an ever-growing need to generate reliable schedules and increase customer satisfaction, the minimization of the total tardiness of all jobs is examined as an optimization criterion of practical relevance. For the purposes of providing a detailed structural description of the problem under study, on the one hand, and detecting the current boundaries of exact solvability, on the other hand, the blocking job shop scheduling problem with total tardiness minimization (BJSPT) is comparatively modeled by two mathematical formulations. Significantly smaller numbers of required variables and constraints in the optimization program can be reported for one type of sequence-defining variables in contrast to the other. In line with this observation, the computational results obtained by a state-of-the-art mixed-integer programming solver clearly indicate the advantages of the usage of binary ordering variables for all pairs of operations of different jobs requiring the same machine. Furthermore, the experiments show that the capability of exact general-purpose solution techniques do not meet the practical conditions in solvable problem size, solution quality and runtime. Additionally, several instance key measures are proposed in order to characterize the given problems and detect relationships between specific values and required computational effort in the solving process. Based on the results, it can be pointed out that the mean machine utilization rate and the mean machine slack constitute good indicators for the complicatedness of a BJSPT, even though more complex figures are still needed to cover the full range of effects. The thesis mainly contributes to the research in complex job shop scheduling by introducing and applying a permutation-based heuristic to the BJSPT. First, different classical encodings of a schedule are discussed with respect to redundancy and feasibility. A procedure to construct a feasible schedule from any given permutation of all operations is presented. Subsequently, three different neighborhood structures, which are based on widely-used operators such as interchanges of adjacent operations on a machine and shifts of operations in the permutation, are defined. It is observed that interchange-based moves cause significant feasibility issues in the construction of neighboring schedules. Therefore, an advanced repair technique is proposed to generate a feasible schedule, which incorporates the predefined move and does not feature a structure arbitrarily different from the initially given solution. Together with this modification scheme, all neighborhoods are applicable in metaheuristic methods to solve the BJSPT, even if the connectivity property cannot be shown due to the involved real-world conditions. The computational results obtained by a simulated annealing algorithm provide empirical evidence for the advantageousness of the usage of a permutation-based heuristic method to find good schedules for the BJSPT in reasonable computation time. Furthermore, it is shown that the problem under study features a fairly rugged search space, a reduction of the set of neighbors is not favorable and the execution of several independent runs of the heuristic procedure is bene- cial. However, the applied heuristic solution technique cannot compete with the mixed-integer programming solver in solution quality and computation time for small instances. Moreover considering problems of large size, the heuristically determined feasible schedules improve the results obtained by solving the mathematical models, but the solution quality is not yet satisfactory for practical applications. This is why the idea of combining promising components and beneficial effects of both solution approaches is pursued. As a pioneering work in this field, a matheuristic technique is proposed for and tested on the BJSPT. Purely mixed-integer programming-based construction schemes and neighborhood structures, which involve solving reduced optimization programs, are integrated into a heuristic framework. Extensive preliminary experiments are conducted to evaluate the individual capability of the most well-known general and scheduling-tailored methods. The best performing mechanisms are accordingly chosen as components of a variable neighborhood search. The computational results clearly highlight matheuristic techniques as a favorable research direction in job shop scheduling. The hybrid solution scheme outperforms the general-purpose solver and the permutation-based heuristic in solution quality and computation time on the given benchmark instances. Overall, two new solution approaches for the BJSPT are proposed generating high quality schedules for instances of previously critical size. Comprehensive empirical and theoretical studies on the internal structures of models and techniques reveal reasons for the difficulties in solving the problem under study and shed light onto the impact of real-world conditions. Enhancements in research on job shop scheduling are reported and first steps into a promising research direction are made. Altogether, the thesis gives rise to novel options in the development of advanced decision support systems for complex planning situations.

Die Planung verschiedenster Arbeitsabläufe stellt eine tägliche Herausforderung in vielen Unternehmen dar. Komplexe Entscheidungen bezüglich der Verteilung unterschiedlicher Ressourcen und der dazugehörigen Bearbeitungsreihenfolge von Aufgaben müssen getro en werden. Insbesondere bei der Herstellung individualisierter Güter und im Betrieb von Logistiksystemen mit hoher Kapitalbindung spielen e ziente Ablaufpläne eine wichtige Rolle für den langfristigen ökonomischen Erfolg eines Unternehmens. Aus diesem Grund verfolgen Forscher im Bereich des Scheduling seit vielen Jahrzehnten das ambitionierte Vorhaben einer verlässlichen Entscheidungsunterstützung für strategische Planer. Während einige klassische Probleme des Scheduling gut verstanden sind, fehlen wissenschaftliche Untersuchungen zur Betrachtung vieler praktischer Bedingungen und Ziele. Um diesen Forschungsbereich mit einer fundierten Studie zu erweitern, wird eine praxisrelevante Klasse von Job Shop Scheduling Problemen umfassend in Bezug auf die Grenzen der Lösbarkeit mit exakten Verfahren der gemischt-ganzzahligen Optimierung, die Anwendbarkeit von bekannten heuristischen Methoden und die Vorteilhaftigkeit von hybriden matheuristischen Ansätzen untersucht. Das Job Shop Problem ist als kombinatorisches Optimierungsproblem von auÿergewöhnlicher Schwierigkeit bekannt, für das selbst einfache Varianten als NP-schwer klassi ziert sind. Eine Menge von Aufträgen ist von einer Menge von Maschinen zu bearbeiten, wobei jeder Auftrag eine individuelle technologische Reihenfolge des Arbeitsablaufs verlangt. Ein einzelner Bearbeitungsschritt eines Auftrags wird als Operation bezeichnet, die mit einer Bearbeitungszeit und der notwendigen Maschine gegeben ist. Um praxisrelevante Bedingungen zu integrieren, ist ein Bereitstellungszeitpunkt für jeden Auftrag de niert, und die wiederholte Bearbeitung eines Auftrags auf einer Maschine ist erlaubt. Das Fehlen von Zwischenlagermöglichkeiten im Planungssystem wird als spezielle Einschränkung betrachtet, die beispielsweise bei der Produktion auÿergewöhnlich groÿer Güter sowie in automatisierten Lagerkonzepten und schienenbasierten Logistiksystemen zu nden ist. Ein Ablaufplan muss bestimmt werden, der allen Operationen der Aufträge die verfügbaren Arbeitszeiten der benötigten Maschinen zuordnet, so dass die gegebenen Restriktionen erfüllt sind. Motiviert durch das fortwährende Bestreben nach verlässlichen Ablaufplänen und steigender Kundenzufriedenheit wird die Minimierung der Gesamtverspätungszeit als praxisorientiertes Optimierungskriterium untersucht. Um eine detaillierte theoretische Beschreibung des betrachteten Problems zu geben und anschlieÿend die aktuell bestehenden Grenzen der exakten Lösbarkeit auszuloten, wird das Job Shop Problem mit Blockierungsbeschr änkungen und der Minimierung der Gesamtverspätungszeit (BJSPT) vergleichend mit zwei mathematischen Formulierungen modelliert. Für einen der beiden Typen von verwendeten, die Reihenfolge de nierenden Variablen kann eine erheblich kleinere Anzahl notwendiger Unbekannter und Nebenbedingungen im Optimierungsmodell festgestellt werden. Übereinstimmend zeigen auch die mit einem der modernsten Lösungsverfahren für gemischt-ganzzahlige Probleme erhaltenen Ergebnisse klare Vorteile der Nutzung von binären Ordnungsvariablen für alle Paare von Operationen unterschiedlicher Jobs, die die gleiche Maschine verlangen. Auÿerdem belegen die Experimente, dass die Leistungsfähigkeit von allgemeinen exakten Lösungstechniken die praktischen Anforderungen in der handhabbaren Problemgröÿe, der Qualität der Ablaufpläne und der Rechenzeit nicht erfüllen kann. Des Weiteren werden einige Problemkennzahlen eingeführt, um die gegebenen Instanzen zu charakterisieren und Verbindungen zwischen bestimmten Ausprägungen und dem erforderlichen Rechenaufwand im Lösungsprozess herzustellen. Basierend auf den Ergebnissen kann beobachtet werden, dass die durchschnittliche Nutzungsrate und die mittlere Pu erzeit der Maschinen gute Indikatoren für den Schwierigkeitsgrad eines Problems darstellen, auch wenn komplexere Kenngröÿen zur vollständigen Beschreibung aller Interdependenzen notwendig sind. Der maÿgebliche Beitrag dieser Arbeit zur Forschung an komplexen Job Shop Problemen besteht in der Einführung eines permutationsbasierten Näherungsverfahrens und dessen Anwendung auf das BJSPT. Nach der Diskussion verschiedener klassischer Darstellungsformen von Ablaufplä- nen, in Bezug auf auftretende Redundanz und Unzulässigkeit, wird ein Verfahren zur Konstruktion eines zulässigen Plans aus jeder beliebigen Liste aller Operationen präsentiert. Anschlieÿend werden drei Nachbarschaftsstrukturen de niert, die auf bekannten Operatoren wie dem Austausch zweier benachbarter Operationen auf einer Maschine und der Verschiebung einer Operation in der Permutation beruhen. Es ist festzustellen, dass austauschbasierte Übergänge erhebliche Probleme in der Zulässigkeit der resultierenden Nachbarlösung verursachen. Hierfür wird ein komplexes Reparaturverfahren konstruiert, das stets einen zulässigen Ablaufplan erzeugt, der den gegebenen Austausch enthält und in seinem Aufbau nicht willkürlich von der Anfangslösung abweicht. Mit dieser Reparaturmethode können alle beschriebenen Nachbarschaften in Metaheuristiken eingebettet und auf das BJSPT angewendet werden, auch wenn aufgrund der praxisrelevanten Bedingungen der theoretische Zusammenhang für keine der Strukturen gegeben ist. Die mit einem Simulated Annealing erzielten Rechenergebnisse unterstützen empirisch die Zweckmäÿigkeit der Nutzung einer permutationsbasierten Heuristik zur Generierung guter Ablaufpläne für das BJSPT in vertretbarer Laufzeit. Auÿerdem zeigt sich, dass das betrachtete Problem einen eher zerklüfteten Lösungsraum aufweist, dass eine Reduktion der Anzahl zu betrachtender Nachbarn nicht vorteilhaft ist und dass sich die Ausführung mehrerer unabhängiger Durchläufe des heuristischen Verfahrens positiv auswirkt. Dennoch kann die angewendete Heuristik besonders für kleine Instanzen nicht mit der erreichten Qualit ät der Ablaufpläne und der benötigten Rechenzeit des exakten Lösungsverfahrens konkurrieren. Bei der Betrachtung groÿer Instanzen weisen die heuristisch erzielten Pläne zwar bessere Zielfunktionswerte auf als die der exakten Methode, jedoch genügt die Lösungsqualität den Anforderungen einer realen Planungssituation noch nicht. Aus diesem Grund scheint die Idee der Kombination von vorteilhaften Komponenten und positiven Effekten der beiden Ansätze erfolgversprechend. Als erster Vorstoÿ in diesem Forschungsfeld wird ein matheuristisches Verfahren für das BJSPT konstruiert und getestet. Auf rein gemischtganzzahliger Programmierung basierende Konstruktionsschemata und Nachbarschaften, die das wiederholte Lösen von reduzierten Optimierungsmodellen erfordern, werden in eine heuristische Struktur eingebettet. Umfangreiche vorgelagerte Experimente erlauben zunächst die Bewertung der individuellen Leistungsfähigkeit der meist genutzten, allgemeinen und auf das Scheduling zugeschnittenen Verfahren. Darauf aufbauend werden die vielversprechendsten Methoden als Komponenten für eine variable Nachbarschaftssuche gewählt. Die erzielten Rechenergebnisse belegen deutlich, dass die Anwendung von Matheuristiken eine zukunftsweisende Forschungsrichtung im Bereich des Job Shop Scheduling ist. Das hybride Lösungsverfahren übertri t sowohl die allgemeine gemischt-ganzzahlige Optimierung und als auch die permutationsbasierte Metaheuristik in der Qualität der generierten Ablaufpläne und der notwendigen Rechenzeit für die gegebenen Vergleichsinstanzen. Insgesamt werden in dieser Arbeit zwei neue Lösungsansätze für das BJSPT präsentiert, die die Generierung von Ablaufplänen hoher Qualität für Instanzen mit vorherig kritischer Problemgröÿe ermöglichen. Umfassende empirische und theoretische Untersuchungen von Strukturen der Modelle und Methoden legen Gründe für die Schwierigkeiten in der Lösung der betrachteten Probleme o en und geben Aufschluss über die Auswirkungen von praxisrelevanten Bedingungen. Entwicklungen im Bereich des Job Shop Scheduling sind erzielt und erste Schritte in einer vielversprechenden Forschungsrichtung sind getan. Die Arbeit bietet damit neue Möglichkeiten für die Entwicklung verbesserter Systeme zur Entscheidungsunterstützung für komplexe Planungssituationen.