TU Darmstadt / ULB / TUprints

Models and optimization techniques for intralogistic problems in part supply

Polten, Lukas (2021):
Models and optimization techniques for intralogistic problems in part supply. (Publisher's Version)
Darmstadt, Technische Universität,
DOI: 10.26083/tuprints-00017886,
[Ph.D. Thesis]

Available under CC-BY-SA 4.0 International - Creative Commons, Attribution Share-alike.

Download (17MB) | Preview
Item Type: Ph.D. Thesis
Status: Publisher's Version
Title: Models and optimization techniques for intralogistic problems in part supply
Language: English

Products must be manufactured before the consumer can use them. Most products are not created from nothing, but are made from raw materials or components. For a product to be manufactured, the components must be on site at in time for assembly. The processes required for this can be carried out particularly efficiently and resource-sparingly if they are well planned. The four publications that make up this cumulative dissertation deal with the mathematical models and algorithms required for planning these processes.

All publications deal with problems that are motivated by intralogistic issues related to parts supply. This means that they deal with problems where components have already arrived at the factory premises and now have to be at the right place at the right time for assembly.

Some products are manufactured from raw materials that are delivered in large loads and therefore are stored on the company premises. For other products the parts are delivered just before assembly. This practice is called the just-in-time principle. It is often used when several variants of a product are manufactured on the same assembly line. The best example is when different models are produced on the same assembly line in the automotive industry.

The scientific publications in this thesis deal with selected parts of the processes, how the warehouses operate and how the parts are transported from there to the correct assembly station.

The publications are preceded by an introduction that places them in a common scientific context. Subsequently, the first publication deals with the delivery of goods from the warehouse in the factory to the assembly line. The following publications deal with problems motivated by the storage and retrieval of goods in warehouses. The first three publications have already been published. Here is a short summary of the individual papers.

The first paper deals with the planning of the loading of tow trains to periodically deliver parts from a central depot at fixed times to the stations along the assembly line of a factory. The parts must be delivered before they are needed on the assembly line. A difficulty arises from the fact that the parts are stored in containers with several identical parts. The objective is to prevent, if possible, the accumulation of many half-full packages at the stations. The packages with the parts are delivered as late as possible in any optimal plan. Therefore, the trains are loaded with the parts that are needed in the following time period. The required parts are determined by the models to be produced on the assembly line. The production program is already determined at the time of planning. However, the required parts can be changed in each time period by adjusting the order in which the models pass through the assembly line. The publication refers to this problem as the just-in-time assembly line sequencing problem. The problem is to determine the order in which products are put on the assembly line. Traditionally, sequences are often optimized with the goal of leveling the parts demand. However, this approach does not necessarily work well when parts are delivered in large quantities at fixed times. The publication proposes an exact solution to this problem, based on combinatorial Benders decomposition as well as on bounding procedures and heuristics. It is shown that the algorithm works well on instances from the literature as well as on new data sets. Since this is a new model for a known problem, the relationship between classical level scheduling methods and the new approach is also investigated. In particular, it is analyzed whether the classical models are suitable to reduce the inventory in an assembly system that is supplied by a tow train. The hypothesis that the new model is more suitable can be supported by this comparison.

The other publications deal with various problems of storage and retrieval of goods in warehouses. The focus is on problems from factory warehouses. The second publication deals with autonomous guided vehicles. The other two publications look at automated storage and retrieval systems and differ in the objective and the capacity of the machine that moves the goods in the warehouse. Both articles use assumptions to be able to apply advanced optimization techniques. In the third article this assumption is the dominance of the longest path and in the fourth article it is the "2n-Tour assumption". In the following, these articles are summarized.

The second paper deals with a new problem regarding autonomous guided vehicles in narrow aisle warehouses. Goods have to be stored and retrieved with the help of autonomous guided vehicles. These driver-less forklifts can independently pick up and store away goods from the rack and transport them to or from a picking station. All orders should be processed as quickly as possible. The main obstacle is the narrow aisles, which make it impossible for the vehicles to pass each other inside the aisles. Planning access to the aisles is therefore essential. Two strategies are developed to control access to the aisles. Suitable models are developed and formulated as a mixed integer program. In addition, the complexity of the models is investigated and a large neighborhood search is developed to solve the models. This provides solutions for instances with hundreds of individual orders in a short period of time, which are on average within 2.5 % of the optimal solution. It also analyzes how the design of the warehouse affects the efficiency of the system. In particular, heuristics are used to gain insight into the best access policy, the effect of the number of AGVs, and the optimal layout of warehouses with very narrow aisles.

In the third publication, an automated storage and retrieval system is used to investigate a grouping or batching problem. Batching problems deal with the question of which jobs should be executed together. The problem is to schedule a series of jobs on a single batching machine. Each order has a due date. The goal is to minimize the maximum delay. Additionally, orders have priority relationships and incompatibilities. This model for a single batching machine has many applications. In this paper, we will focus on planning a single crane in an automated storage and retrieval machine, and ask the following questions: Which jobs should be processed together in the same double command cycle when a series of transport requests are involved? In what order should the cycles be processed? Since storage and retrieval requests can refer to the same physical object, priority relationships must be considered. In addition, the crane may not be able to process multiple storage or retrieval requests in the same cycle. Incompatibilities must therefore be taken into account. For example, a crane with capacity one cannot handle two storage requests in the same command cycle. For the sake of simplicity, it is assumed that when storing and retrieving goods, the longest processing time determines the total processing time and the other times can be neglected. This central assumption allows solving a routing problem as a batching problem. A novel exact algorithm is presented, which is based on Branch & Benders Cut and has been proven to solve even large instances with more than 100 jobs in many cases in an optimal way. For the special case without precedence restrictions and incompatibilities, it improves some of the best known solutions from literature.

The fourth publication also deals with an automatic storage and retrieval system. In a split storage system, the articles to be stored are not assigned to specific shelf locations in advance. This system has a crane that can transport several unit load. The assumption in the third article can therefore no longer be made here. Instead, the so-called "2n tour assumption" is made. It requires that each command cycle is as follows: At the beginning the crane is fully loaded with the items to be stored. Then an empty shelf is accessed and an item is stored. Now all the shelves containing an item to be stored are visited. This is removed from the warehouse. Then an object to be stored is placed in its place. For a series of storage and retrieval requests, the planning problem is to decide which requests are to be processed together in the same tour and to determine the order in which the requests are processed. In addition, each storage request is assigned to an available space on the shelf. The goal is to process all requests as quickly as possible. The problem is formulated as a special type of routing problem. Some open questions regarding the time complexity of the related routing problems are answered. The reformulation makes it possible to draw on the rich and mature route planning toolbox from the literature and propose a new exact solution method for the model. It is shown that this method is capable of solving large instances in an optimal way, thus surpassing previous methods from the literature. The new approach is used to derive a wide range of findings. In particular, it is shown that the system throughput can be predicted from the capacity of the crane using a simple rule. Furthermore, the optimal shape of a rack is determined and the ideal planning horizon for rolling planning is investigated. Finally, it is shown how the approach can easily be extended to solve a whole family of related planning problems.

Alternative Abstract:
Alternative AbstractLanguage

Produkte müssen hergestellt werden, bevor der Käufer sie nutzen kann. Dabei werden die meisten Produkte nicht aus dem Nichts erschaffen, sondern aus Rohstoffen oder Bauteilen hergestellt. Damit ein Produkt erfolgreich hergestellt werden kann, müssen die Bauteile zum Herstellungszeitpunkt vor Ort sein. Die dazu nötigen Prozesse können besonders effizient und ressourcenschonend durchgeführt werden, wenn sie gut geplant sind. Von den zur Planung nötigen mathematischen Modellen und Algorithmen, um die Modelle zu lösen, handeln die vier Publikationen, aus denen diese kumulative Dissertation besteht.

Alle Veröffentlichungen befassen sich mit Problemen, die durch intralogistische Fragestellungen rund um die Teilebereitstellung motiviert sind. Das heißt, es geht um Probleme, bei denen Bauteile bereits auf dem Betriebsgelände angekommen sind und nun zum richtigen Zeitpunkt zur Montage am richtigen Ort sein müssen.

Manche Produkte werden aus Rohstoffen hergestellt , die in großen Ladungen geliefert werden und deshalb auch auf dem Betriebsgelände bevorratet werden. Für andere Produkte werden die Teile erst kurz vor dem Zusammenbau angeliefert. Dieses Vorgehen wird als Just-in-time Prinzip bezeichnet. Dieses findet häufig Anwendung, wenn mehrere Varianten eines Produkts auf dem selben Fließband gefertigt werden. Das beste Beispiel sind verschiedene Modelle, die in der Automobilindustrie die selbe Fertigungsstraße durchlaufen.

Um ausgewählte Teile der Prozesse, wie die Warenlager betrieben werden und von dort zur richtigen Montagestation kommen, handeln die wissenschaftlichen Veröffentlichungen in dieser Arbeit.

Den Publikationen ist eine Einleitung vorangestellt, die diese in einen gemeinsamen wissenschaftlichen Kontext einordnet. Anschließend beschäftigt sich die erste Veröffentlichung mit der Lieferung von Waren vom Lager im Betrieb zum Fließband. Die folgenden Publikationen befassen sich mit Problemen, die durch die Ein- und Auslagerung von Waren in Lagerhäusern motiviert sind. Die ersten drei Publikationen wurden bereits veröffentlicht. Hier folgt nun eine kurze Zusammenfassung der einzelnen Beiträge.

Der erste Beitrag befasst sich mit der Planung der Beladung von Schleppzügen, um periodisch Teile aus einem Zentraldepot zu festen Zeiten zu den Stationen entlang des Fließbands einer Fabrik zu liefern. Die Teile müssen angeliefert werden, bevor sie am Montageband benötigt werden. Eine Schwierigkeit ergibt sich aus der Tatsache, dass die Teile in Behältern mit mehreren identischen Teilen gelagert werden. Nun soll nach Möglichkeit verhindert werden, dass sich an den Stationen viele halbvolle Pakete ansammeln. Die Pakete mit den Teilen werden optimaler Weise immer so spät wie möglich angeliefert. Darum ergibt sich, dass die Züge mit den Teilen beladen werden, die im jeweiligen Zeitabschnitt benötigt werden. Die benötigten Teile ergeben sich aus den auf dem Fließband herzustellenden Werken. Das Produktionsprogramm ist zum Planungszeitpunkt bereits festgelegt. Jedoch lässt sich der Teilebedarf in jedem Zeitabschnitt ändern, indem die Reihenfolge angpasst wird, in der die Modelle das Fließband durchlaufen. Die Veröffentlichung spricht hier vom Problem der Sequenzierung von Fließbändern. Das Problem der Sequenzierung von Fließbändern besteht darin, die Reihenfolge zu bestimmen, in der eine bestimmte Menge von Produkten am Fließband auf den Weg gebracht wird. Klassischerweise werden die Sequenzen oft mit dem Ziel optimiert, den Teilebedarf zu nivellieren. Dieser Ansatz funktioniert jedoch nicht unbedingt gut, wenn Teile zu festen Zeitpunkten in großen Mengen geliefert werden. In der Veröffentlichung wird für dieses Problem eine exakte Lösungsmethode vorgeschlagen, die auf der kombinatorischen Benders Zerlegung sowie auf Bounding-Verfahren und Heuristiken basiert. Es hat sich gezeigt, dass die Algorithmen sowohl auf Instanzen aus der Literatur als auch auf neuen Datensätzen gut funktionieren. Da es sich um ein neues Modell für ein bekanntes Problem handelt, wird auch das Verhältnis zwischen klassische Level Scheduling-Methoden und dem neuen Ansatz untersucht. Dabei wird insbesondere analysiert, ob die klassischen Modelle geeignet sind um den Bestand in einem Montagesystem zu reduzieren, das mit einem Schleppzug beliefert wird. Die Hypothese, dass das neue Modell besser geeignet ist, kann mit diesem Vergleich untermauert werden.

Die übrigen Publikationen befassen sich mit verschiedenen Problemen der Ein- und Auslagerung von Waren in Warenlagern. Dabei liegt der Fokus auf Problemen aus Warenlagern von Fabriken. Die zweite Publikation beschäftigt sich mit autonomen Gabelstaplern. Die anderen beiden Veröffentlichungen betrachten automatisierte Regalsysteme und unterscheiden sich in der Zielsetzung und der Kapazität der Maschine, die die Waren im Lager bewegt. Beide Artikel nutzen Annahmen, um hochentwickelte Optimierungstechniken einsetzen zu können. Im dritten Artikel ist diese Annahme die Dominanz des längsten Weges und im vierten Artikel ist es die "2n-Tour-Annahme". Im Folgenden werden diese Artikel zusammengefasst.

Die zweite Veröffentlichung befasst sich mit einem neuen Problem zu fahrerlosen Transportsystemen in Schmalganglagern. Waren müssen mit Hilfe von autonomen Gabelstaplern ein- und ausgelagert werden. Die fahrerlosen Gabelstapler können die Waren selbständig aus dem Regal aufnehmen und wieder einlagern und sie zu oder von einem Kommissionierplatz transportieren. Alle Aufträge sollen so schnell wie möglich bearbeitet werden. Das Haupthindernis sind die engen Gänge, die es den Fahrzeugen unmöglich machen, innerhalb der Regale aneinander vorbeizufahren. Deshalb ist die Planung des Zugangs zu den Regalgängen unerlässlich. Es werden zwei Strategien zur Kontrolle des Zugangs zu den Regalen entwickelt. Es werden passende Modelle entwickelt und als gemischt ganzzahliges Programm formuliert. Außerdem wird die Komplexität der Modelle untersucht und eine große Nachbarschaftssuche zur Lösung der Modelle entwickelt. Diese liefert für Instanzen mit Hunderten von Einzelaufträgen in kurzer Zeit Lösungen, die im Durchschnitt innerhalb von 2,5 % der optimalen Lösung liegen. Es wird auch analysiert, wie sich die Gestaltung des Warenlagers auf die Effizienz des Systems auswirkt. Insbesondere wird die Heuristik verwendet, um Einblicke in die beste Zugangspolitik, in die Auswirkung der Anzahl der AGVs, sowie in die optimale Anordnung von Lagern mit sehr engen Gängen zu erhalten.

In der dritten Veröffentlichung wird ein automatisiertes Speicher- und Abrufsystem zum Anlass genommen, um ein Gruppierungs oder Batchingproblem zu untersuchen. Batchingprobleme befassen sich mit der Frage, welche Aufträge gemeinsam ausgeführt werden können. Das Problem ist die Planung einer Reihe von Aufträgen auf einer einzigen Batchingmaschine. Jeder Auftrag hat eine Fälligkeit. Das ziel ist es, die maximale Verspätung zu minimieren. Zusätzlich haben Aufträge Vorrangbeziehungen und Inkompatibilitäten. Dieses Belegungsplanungsmodell für eine einzelne Batchingmaschine hat viele Anwendungsmöglichkeiten. Es wird sich in dieser Veröffentlichung auf die Planung eines einzelnen Krans in einem automatisierten Regalbediengerät konzentriert.Dabei stellen sich folgende Fragen: Welche Aufträge sollten angesichts einer Reihe von Transportaufträgen zusammen im selben Doppelbefehlszyklus verarbeitet werden? In welcher Reihenfolge sollten die Zyklen abgearbeitet werden? Da sich Ein- und Auslagerungsanforderungen auf denselben physischen Gegenstand beziehen können, müssen Vorrangbeziehungen beachtet werden. Darüber hinaus ist der Kran möglicherweise nicht in der Lage, mehrere Ein- oder Auslagerungsanforderungen im selben Zyklus zu bearbeiten. Deshalb müssen Inkompatibilitäten berücksichtigt werden. So kann ein Kran mit Kapazität eins nicht zwei Einlagerungsaufträge im selben Befehlszyklus Durchführen. Der Einfachheit halber wird davon ausgegangen, dass beim Ein- und Auslagern von Gütern die längste Verarbeitungszeit die Gesamtverarbeitungszeit bestimmt und die anderen Zeiten vernachlässigt werden können. Diese zentrale Annahme erlaubt es uns, ein Routingproblem als Batchingproblem zu lösen. Es wird ein neuartiger exakter Algorithmus vorgestellt, der auf Branch & Benders Cut basiert und nachweislich selbst große Instanzen mit mehr als 100 Jobs in vielen Fällen optimal löst. Für den Spezialfall ohne Vorrangbeschränkungen und Inkompatibilitäten verbessert er einige der bekanntesten Lösungen aus der Literatur.

Die vierte Veröffentlichung befasst sich ebenfalls mit einem automatischen Ein- und Auslagerungssystem. In einem geteilten Lagersystem werden die einzulagernden Artikel nicht im Voraus bestimmten Regalplätzen zugeordnet. Dieses System verfügt über einen Kran, der mehrere Ladeeinheiten transportieren kann. Die Annahme im dritten Aufsatz kann daher hier nicht mehr getroffen werden. Stattdessen wird die so genannte "2n-Tour-Annahme" getroffen. Zu Beginn ist der Kran vollständig mit den einzulagernden Gegenständen beladen. Dann wird auf ein leeres Regal zugegriffen und ein Gegenstand eingelagert. Nun werden alle Fächer aufgesucht, die einen einzulagernden Gegenstand enthalten. Dieser wird aus dem Lager entfernt. Anschließend wird ein einzulagernder Gegenstand an dessen Stelle gestellt. Bei einer Reihe von Ein- und Auslagerungsanfragen besteht das Planungsproblem darin, zu entscheiden, welche Anfragen zusammen in derselben Tour bearbeitet werden und die Reihenfolge festzulegen, in der die Anforderungen bearbeitet werden. Außerdem wird jede Einlagerungsanforderung einem verfügbaren Platz im Regal zugeordnet. Das Ziel ist es, alle Aufträge so schnell wie möglich zu bearbeiten. Das Problem wird als eine spezielle Art von Routenplanungs-Problemen formuliert. Einige offene Fragen bezüglich der zeitlichen Komplexität bezüglich der damit verbundenen Routing-Probleme werden beantwortet. Die Neuformulierung ermöglicht es, auf die reichhaltige und ausgereifte Routenplanungs-Toolbox aus der Literatur zurückzugreifen, um einen neuen exakten Lösungsansatz für das Modell vorzuschlagen. Es wird gezeigt, dass diese Methode in der Lage ist, große Instanzen optimal zu lösen und damit frühere Methoden aus der Literatur zu übertreffen. Der neue Ansatz wird verwendet, um vielfältige Erkenntnisse abzuleiten. Insbesondere wird gezeigt, dass der Systemdurchsatz anhand einer einfachen Regel aus der Kapazität des Krans vorhergesagt werden kann. Weiterhin wird die optimale Form eines Regals bestimmt und der idealen Planungshorizont bei rollierender Planung untersucht. Schließlich wird gezeigt, wie der Ansatz sich leicht erweitert lässt, um eine ganze Familie von verwandten Planungsproblemen zu lösen.

Place of Publication: Darmstadt
Collation: XX, 209 Seiten
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
300 Sozialwissenschaften > 330 Wirtschaft
Divisions: 01 Department of Law and Economics > Betriebswirtschaftliche Fachgebiete > Fachgebiet Produktion und Supply Chain Management
Date Deposited: 04 May 2021 13:22
Last Modified: 04 May 2021 13:23
DOI: 10.26083/tuprints-00017886
URN: urn:nbn:de:tuda-tuprints-178869
Referees: Glock, Prof. Dr. Christoph and Emde, Prof. Dr. Simon
Refereed: 29 January 2021
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/17886
Actions (login required)
View Item View Item