Analysis of idle time and waiting time as objective functions and the influence of processing times in permutation flow shop scheduling

Maassen, Kathrin GND

Der Grundgedanke des Lean Managements ist die Beseitigung aller Arten von Verschwendung in einem Produktionssystem. Wird diese Idee auf das operative Produktionsmanagement übertragen, hier im speziellen auf die Fließfertigungsplanung, führt dies zur Eliminierung von zeitlicher Verschwendung innerhalb des Produktionsprozesses. Zeitliche Verschwendung entsteht, wenn Maschinen auf den nächsten Auftrag (Leerlaufzeit) oder Aufträge vor einer Maschine auf ihre Bearbeitung warten müssen (Wartezeit). Beide Situationen führen entweder zu einer geringeren Auslastung der Maschinen oder zu einem unterbrochenen Auftragsfluss. Um eine hohe Auslastung bzw. einen reibungslosen Auftragsfluss zu gewährleisten, können die Ziele der Minimierung der Gesamtkernleerlaufzeit bzw. der Gesamtkernwartezeit angewendet werden. Die umfangreiche Literaturrecherche zeigt jedoch, dass beide Zielfunktionen bisher nur selten analysiert wurden, obwohl sie von hoher praktischer Relevanz im Lean Management sind. Daher konzentriert sich diese Dissertation auf die Minimierung dieser beiden Ziele in Fließfertigungssystemen, indem detaillierte Untersuchungen von Literatur und Theorie sowie empirischen Studien durchgeführt werden.

In der Fließfertigungsplanung wird eine bestimmte Anzahl von Aufträgen auf eine bestimmte Anzahl von Maschinen eingeplant. Die Maschinen sind dabei in einer Reihe angeordnet. Die am häufigsten untersuchten Ziele sind die Minimierung der Gesamtbearbeitungszeit und der Durchlaufzeit. Die Gesamtbearbeitungszeit wird als Fertigstellungszeitpunkt des gesamten Zeitplans definiert, während sich die Durchlaufzeit auf die Summe aller Fertigstellungszeitpunkte bezieht. Die Minimierung der Gesamtbearbeitungszeit hat eine hohe Maschinenauslastung zur Folge, während die Minimierung der Durchlaufzeit einen hohen Auftragsfluss erzielt. In dieser Arbeit werden die Gemeinsamkeiten und Unterschiede zwischen den beiden auslastungsorientierten Zielen, der Gesamtbearbeitungszeit und der Kernleerlaufzeit, und den auftragsflussorientierten Zielen, der Durchlaufzeit und der Kernwartezeit, analysiert. Darüber hinaus wurden in der Literatur häufig Restriktionen in Kombination mit der Minimierung der Gesamtbearbeitungszeit und Durchlaufzeit untersucht, die keine Leerlauf- oder Wartezeiten gestattet. Es wird daher analysiert, ob diese Restriktionen durch eine reine Minimierung der Kernleerlaufzeit bzw. der Kernwartezeit vereinfacht werden können.

Da die Kernleerlaufzeit und die Kernwartezeit bisher selten analysiert wurden, wird die Rechenkomplexität untersucht und es wird nachgewiesen, dass beide Ziele NP-schwer für mehr als zwei Maschinen sind. Darüber hinaus werden die Ziele mit der Gesamtbearbeitungszeit und der Durchlaufzeit verglichen, indem exakte Lösungsmethoden für eine Reihe von kleinen (max. 20 Aufträge) Probleminstanzen angewendet werden. Die Eingabedaten, hier die Bearbeitungszeiten, werden zufällig und mittels Gleichverteilung generiert. Es wird gezeigt, dass die beiden Zielpaare, sowohl auslastungsorientiert als auch auftragsflussorientiert, zwar ähnlich, aber nicht identisch sind, wobei die Kongruenz zwischen Durchlaufzeit und Kernwartezeit stärker ist. Außerdem besteht ein Zielkonflikt zwischen Kernwartezeit und Kernleerlaufzeit. Große Probleminstanzen, hier mehr als 20 Aufträge, können aufgrund der NP-Schwere nicht optimal in angemessener Zeit gelöst werden. Daher werden die, in der Literatur angewendeten, konstruktiven Heuristiken und Meta-Heuristiken für die klassischen Ziele (Minimierung der Gesamtbearbeitungszeit und Durchlaufzeit) in Bezug auf Kernwartezeit und Kernleerlaufzeit modifiziert und zur effizienten Lösung von großen Probleminstanzen eingesetzt.

Kernleerlaufzeit und Kernwartezeit sind Ziele mit Praxisbezug im Lean Management. Daher wird ebenfalls der Einfluss von realitätsnahen und strukturierten Bearbeitungszeiten auf beide Ziele analysiert. Zunächst werden Sonderfälle untersucht, bei denen die Kernleerlaufzeit und die Kernwartezeit triviale Zielfunktionen darstellen oder identisch zur Minimierung der Gesamtbearbeitungszeit und Durchlaufzeit sind. Weiterhin werden Probleminstanzen mit der logarithmischen Normalverteilung generiert, die unterschiedliche Variabilitätsniveaus und Fließfertigungsstrukturen implizieren. Es wird gezeigt, dass Struktur und Variabilität einen stärken Einfluss auf die betrachteten Ziele haben können. Die Beziehungen zwischen Kernwartezeit und Durchlaufzeit sowie zwischen Kernleerlaufzeit und Gesamtbearbeitungszeit, die für gleichverteilte Bearbeitungszeiten ermittelt wurden, gelten jedoch auch für diese Probleme.

Zusammenfassend werden in dieser Dissertation die Ziele der Minimierung der Gesamtkernleerlaufzeit und Gesamtkernwartezeit als Indikatoren für zeitliche Verschwendung innerhalb der Fließfertigungsplanung analysiert. Es wird eine umfangreiche Literaturrecherche durchgeführt und die Komplexität beider Ziele wird analysiert. Darüber hinaus wird die Beziehung zu anderen häufig verwendeten Zielen untersucht, um zu prüfen, ob sich diese Ziele gegenseitig ersetzen können. Weiterhin wird geprüft, ob die Restriktionen vereinfacht werden können, die besagen, dass keine Leerlauf- oder Wartezeit innerhalb des Produktionsprozesses gestattet ist. Für beide Ziele werden heuristische Ansätze zur Lösung großer Problemgrößen entwickelt. Darüber hinaus wird der Einfluss von strukturierten Fließfertigungssystemen in Kombination mit logarithmisch normalverteilten Bearbeitungszeiten bezogen auf Kernleerlauf- und Kernwartezeit analysiert, um realitätsnahe Anwendungen abzubilden.

The basic idea of lean management is to eliminate all kinds of waste in a production system. Transferring this idea to operational production management, and here flow shop scheduling, leads to the elimination of waste of time within the production processes. Wasted time occurs when machines have to wait for the next job to process (idle time) or jobs have to wait in front of a machine for being processed (waiting time). Both situations lead to either less utilization of machines or an interrupted job flow. To ensure a high utilization or smooth job flow, the objectives of minimizing total core idle time or total core waiting time can be applied. However, the extensive literature review shows that both objective functions have only been rarely analyzed so far, although they are of high practical relevance in lean management. Therefore, this doctoral thesis focuses on the minimization of total core idle time and total core waiting time in permutation flow shop scheduling by examining literature and theory as well as conducting empirical studies.

In permutation flow shop scheduling, a set of jobs has to be scheduled to a set of machines which are arranged in series. The most studied objectives are the minimization of makespan and total completion time. Makespan is defined as the completion time of the entire schedule, while total completion time refers to the sum of completion times. The minimization of makespan is related to a high machine utilization, while total completion time is minimized to yield a continuous job flow. In this thesis similarities and differences between the two utilization-oriented objectives, makespan and total core idle time, and job-flow-oriented objectives, total completion time and total core waiting time, are analyzed. Furthermore, in the scheduling literature the constraints of no-idle-time and no-waiting-time in combination with the minimization of makespan and total completion time have often been studied. Therefore, it is analyzed whether both constraints can be relaxed by solely minimizing total core idle time or total core waiting time, respectively.

Since core idle time and core waiting time have rarely been analyzed so far, the computational complexity is examined and it is proven that both objectives are NP-hard for more than two machines. Moreover, the objectives are compared to makespan and total completion time by applying exact solution methods for a set of small (max. 20 jobs) problem instances. The input data, hence processing times, are generated randomly with uniform distribution. It is shown that both objective pairs, utilization-oriented as well as job-flow-oriented, are aligned but not identical, while the alignment between total completion time and core waiting time is stronger. Moreover, a goal conflict exists between core waiting time and core idle time. Large-size problems, here more than 20 jobs, cannot be solved optimally within reasonable time because of the NP-hardness. Therefore, constructive heuristics and meta-heuristics applied in the literature to the classical objectives (makespan and total completion time) are modified in terms of core waiting time and core idle time and used to solve large-size problems efficiently, too.

Core idle time and core waiting time are objectives with practical relevance in lean management. Therefore, the influence of real-life-oriented and structured processing times on both objectives is analyzed. First of all, special cases are examined where core idle time and core waiting time are trivial objective functions or similar to makespan and total completion time. Secondly, problem instances are generated with the logarithmic normal distribution, implying different variability-levels and flow shop structures. It is shown that structure and variability can have a strong influence on the considered objectives. However, the overall alignment between total core waiting time and total completion time, and total core idle time and makespan, which was found with uniformly distributed processing times, can be confirmed.

Summarizing, this doctoral thesis analyzes the objectives of minimizing the total core idle time and total core waiting time as indicators for waste of time in permutation flow shop scheduling. An extensive literature review is carried out and the computational complexity of both objectives is analyzed. Moreover, the relationship to other commonly used objectives is investigated to check whether these objectives could replace each other or whether no-idle or no-wait constraints can be relaxed. Heuristic approaches are developed for both objectives to solve large problem sizes. Moreover, the influence of structured flow shops in combination with logarithmic normally distributed processing times on core idle time and core waiting time are analyzed to refer to real-life-oriented applications.

Cite

Citation style:
Maassen, K., 2020. Analysis of idle time and waiting time as objective functions and the influence of processing times in permutation flow shop scheduling. https://doi.org/10.17185/duepublico/73541
Could not load citation form.

Rights

Use and reproduction:
All rights reserved

Export