Back
Texte intégral
Doctoral thesis

Optimierung automatisierter Kompaktlager in Entwurf und Steuerung

    31.08.2001

258 S

Thèse de doctorat: Université de Fribourg, 2001

English German This thesis investigates the optimization of automated high-density storage systems at design stage and in control logic development. In modern storage technology, automated high-density storage systems offer a space saving alternative to traditional storage rack systems. They comprise several floors subdivided into parallel storage aisles and linking cross-aisles. Pallet movements are computer-controlled and executed by elevators and transfer carriages integrated in each aisle. Layout and operation of a specific warehouse are customer-dependent. Two main issues are investigated. A central problem in designing complex storage systems is to estimate their performance in a reliable way. Performance analysis is needed in order to evaluate various design alternatives differing in size, layout and other parameters. Common performance measures are based on maximum throughput (i.e. number of incoming and outgoing pallets in a given time period). Due to the complexity of automated high-density storage systems, no standard analytical method for performance analysis is available. Also, the use of simulation methods is questionable, not only because of the large number of processes to be simulated, but also because the control logic is often not fully specified at the design stage. In this work, a linear optimization model for performance analysis is developed which is independent of the control system and needs a minimum of input data. The storage system is described by a network model where palette movements are represented by multi-commodity flows. An optimal allocation strategy and resulting processor loads can be calculated by flow optimization, leading to performance upper bounds. This multi-commodity flow model is then enhanced in order to take into account idle processor moves directly affecting processor loads, and pallet sojourn times in the system which affect storage strategy. It is shown that idle processor moves can be modeled via special transportation problems embedded in the flow model. Furthermore, constraints based on Little's formula are introduced in order to link stock levels, pallet sojourn times and throughput. Numerical results show the validity of the model. In addition to calculating performance upper bounds, the model offers support in identifying bottleneck resources and designing efficient storage and routing strategies. The second issue concerns the development of an optimized control logic for automated high-density warehouses. Controlling such storage systems is a complex task involving a multitude of decisions at different levels. Three main logical components can be distinguished: determination of the transportation orders based on the storage and retrieval orders (storage strategy, routing), determination of the relocations (forced relocations, reorganization) and determination of the schedule (sequencing and scheduling of the transportation actions). This thesis focuses on optimizing the control system at the schedule level. An optimization model is developed which generates an optimized schedule based on a given set of transportation orders. The transportation orders determine the actions to be performed by each processor. The model’s objective is to sequence and schedule the actions in order to minimize total makespan. In the following, this problem is referred to as the storage problem. As a first result, it is shown that the set of all admissible schedules (i.e. the solution space) can be fully described by means of conjunctive and disjunctive precedence constraints. A precedence constraint expresses the condition that there must be a given time lag between the starting times of two operations. A disjunctive precedence constraint corresponds to a pair of precedence constraints of which at least one must hold. Models with disjunctive precedence constraints can be formulated as disjunctive graph problems. The nodes represent the operations and the weighted arcs the precedence constraints. Disjunctive precedence constraints correspond to a disjunctive arc set, i.e. a pair of disjunctive arcs of which one has to be selected. Disjunctive graphs are a well-known concept for modeling sequencing problems. Up to now, they have been used mainly in the context of the famous job-shop problem. This problem can be expressed in a disjunctive graph where a complete acyclic selection of disjunctive arcs has to be determined which minimizes the length of a maximal path in the resulting graph. A selection is called complete if it contains at least one arc of each disjunctive set. A distinctive property of disjunctive job-shop graphs is that each disjunctive set contains two arcs with identical extremities but reverse orientation. Modeling the storage problem with disjunctive precedence constraints leads to disjunctive graphs for which this property does not hold. Motivated by this fact, this thesis introduces a generalization of classical disjunctive graphs, allowing disjunctive pairs of arcs with different extremities. The structural properties of generalized disjunctive graphs are studied. A main result is that the feasibility problem for generalized disjunctive graphs - in contrast to the feasibility problem in the job-shop case - is NP-hard. The feasibility problem addresses the question whether a generalized disjunctive graph has an admissible, i.e. complete, positive acyclic selection of disjunctive arcs. Furthermore, it is shown that the feasibility problem is also NP-hard for the disjunctive graphs resulting from the storage problem. This has severe consequences for the design of optimization algorithms for the storage problem and solution methods developed for the job-shop problem cannot be applied to the storage problem. Constructive heuristics like priority dispatch rule methods are hardly applicable since the question whether a partial solution can be extended to an admissible solution is NP-hard. Iterative improvement methods based on the exchange of critical disjunctive arcs are problematic as well since exchanging critical arcs in disjunctive graphs can lead to inadmissible solutions. Bottleneck approaches like the well-known shifting bottleneck algorithm are not applicable because the sequencing of single processors typically produces inadmissible solutions. The design of an appropriate neighborhood for iterative improvement is difficult since, in general, several arcs on different processors have to be exchanged in order to obtain an admissible neighbor solution. A crucial question is which arcs need to be exchanged additionally when exchanging one critical arc. This problem leads to the concept of forced and forbidden arcs. A partial selection forces, respectively forbids a disjunctive arc if all admissible selections including this partial selection must contain, respectively cannot contain this arc. For solving the storage problem, a neighborhood is defined which is based on forced and forbidden arcs and the concept of 1-job-storage-graphs. These graphs are a relaxation of storage graphs in the sense that only disjunctive arcs are considered which are incident to a given job. Of special interest are 1-job-storage-graphs that are conjunctively closed, i.e. in which no forced arcs exist. An important result is that a conjunctively closed, positive acyclic 1-job-storage-graph always has an admissible selection. Moreover, it is shown that the feasibility problem for 1-job-storage-graphs is polynomially solvable and the forced arcs can be calculated in polynomial time. These results allow the design of a relatively complex neighborhood involving the calculation of the forced arcs set in a 1-job-storage-graph and its completion to an admissible selection. Based on this neighborhood, a descent method is devised which improves an existing solution by iteratively exchanging critical arc sets. Numerical results are favorable and demonstrate considerable optimization potential. For realistic problem data and arbitrary starting sequences, schedule improvements in the order of thirty to fifty percent can be achieved in a few minutes of computation time. Die vorliegende Dissertation beschäftigt sich mit der Optimierung automatisierter Kompaktlager in der Phase des Entwurfs und bei der Entwicklung der Lagersteuerung. Automatisierte Kompaktlager bilden in der modernen Lagertechnik eine platzsparende Alternative zu herkömmlichen Zeilenregallagern. Ein automatisiertes Kompaktlager besteht aus mehreren Lagerebenen, welche gegliedert sind in parallel aneinanderliegende Lagerkanäle und rechtwinklig dazu angeordnete Verbindungsquergänge. Der Transport des palettisierten Lagerguts geschieht mit Hilfe von integrierten Kanalfahrzeugen, Quergangwagen und Aufzügen. Im Zusammenhang mit automatisierten Kompaktlagern werden zwei Problemstellungen bearbeitet. In der Entwurfsphase ist die Problematik der Leistungsanalyse von zentraler Bedeutung. Die Evaluation verschiedener Entwurfsalternativen bedingt eine Methodik zur Abschätzung der zu erwartenden Lagerleistung. Als Leistungsmass wird die maximale Anzahl Ein- und Auslagerungen betrachtet, welche in einem bestimmten Zeitraum möglich ist. Auf Simulation basierende Ansätze sind aufgrund der Komplexität der Steuerungsprozesse nur schwer realisierbar. In dieser Arbeit wird ein Lineares Optimierungsmodell für die Leistungsanalyse entwickelt, welches steuerungsunabhängig ist und ein Minimum von Eingabedaten benötigt. Zur formalen Darstellung der Lagersysteme wird ein Netzwerkmodell entworfen, in welchem die Lagerbewegungen als Mehrgüterflüsse dargestellt werden. Durch Flussoptimierung lässt sich die Belastung der Förderprozessoren bei optimaler Allokationsstrategie abschätzen, woraus eine obere Schranke für die Lagerleistung resultiert. Eine Schwierigkeit bei der Abschätzung der Prozessorenbelastung besteht darin, den Aufwand für die reihenfolgeabhängigen Anfahrtswege zu bestimmen. Es wird gezeigt, wie mit Hilfe von speziellen Transportproblemen, welche in das Lineare Programm eingebettet sind, der Leerfahrtenaufwand der Förderprozessoren abgeschätzt werden kann. Als weitere Modellkomponente wird die Lagerstrategie abhängig gemacht von den Verweilzeiten der Paletten im Lager. Auf der Basis des Little’schen Gesetzes wird ein System von linearen Restriktionen entworfen, welches einen Zusammenhang zwischen Lagerbestand, Verweilzeit und Lagerleistung herstellt. Numerische Resultate zeigen die Validität des Modells. Neben der Bestimmung einer oberen Leistungsschranke bietet das Modell Unterstützung bei der Erkennung von Engpass-Ressourcen und beim Entwurf von optimierten Lager-, Routen- und Reorganisationsstrategien. Als zweite Problemstellung beschäftigt sich diese Arbeit mit dem Entwurf einer optimierten Steuerung für automatisierte Kompaktlager. Die Steuerung eines Lagersystems bildet eine komplexe Aufgabe, welche eine Vielzahl von Entscheidungsdimensionen umfasst. Auf der Stufe der dispositiven Steuerung lassen sich drei Hauptfunktionen unterscheiden: Bestimmung der Transportaufträge aufgrund der Ein- und Auslagerungsaufträge (Lagerstrategie, Routenwahl), Bestimmung der Umlagerungen (erzwungene Umlagerungen, Reorganisation) und Bestimmung des Ablaufplans (Reihenfolge und Terminierung der Transportaktionen). In dieser Arbeit wird die Optimierung der Steuerungsprozesse auf der Ebene der Ablaufpläne betrachtet. Es wird ein Optimierungsmodell entwickelt, welches ausgehend von einer Menge von Transportaufträgen einen optimierten Ablaufplan generiert. Durch die Transportaufträge wird für jeden Förderprozessor die Menge der auszuführenden Aktionen vorgegeben. Ziel des Optimierungsmodells ist die Bestimmung der Ausführungsreihenfolge und der Startzeitpunkte dieser Aktionen, so dass die Gesamtdauer des Lagerprozesses (makespan) minimiert wird. Dieses Optimierungsproblem wird im folgenden als Lager-Problem bezeichnet. Als erstes Resultat wird gezeigt, dass sich die Menge aller zulässigen Ablaufpläne (d.h. der Lösungsraum) vollständig beschreiben lässt mit Hilfe von konjunktiven und disjunktiven Präzedenzbedingungen. Eine Präzedenzbedingung besagt, dass zwei Operationen zeitlich nacheinander ausgeführt werden müssen, wobei zwischen den Startzeitpunkten der Operationen eine bestimmte minimale Zeitspanne verstreichen muss. Eine disjunktive Präzedenzbedingung entspricht einem Paar von Präzedenzbedingungen, von denen mindestens eine zutreffen muss. Modelle mit disjunktiven Präzedenzbedingungen lassen sich in Form von disjunktiven Graphen darstellen. Die Knoten repräsentieren die Operationen und die gewichteten Bogen die Präzedenzbedingungen. Disjunktive Präzedenzbedingungen entsprechen einer disjunktiven Bogenmenge, d.h. einem Paar von disjunktiven Bogen, von denen einer ausgewählt wird. Disjunktive Graphen bilden ein bekanntes Konzept zur Modellierung von Reihenfolgeproblemen und wurden bis anhin vor allem im Zusammenhang mit dem Job-Shop-Problem verwendet. Das Job-Shop-Problem lässt sich als disjunktives Graphenproblem darstellen, bei welchem es darum geht, eine vollständige, azyklische Selektion von disjunktiven Bogen zu bestimmen, so dass die Länge eines längsten Weges im resultierenden Graphen minimal ist. Eine Selektion heisst vollständig, wenn sie aus jeder disjunktiven Menge mindestens einen Bogen enthält. Disjunktive Job-Shop-Graphen haben die Eigenschaft, dass die disjunktiven Mengen aus zwei Bogen bestehen, welche dieselben Knoten verbinden, aber entgegengesetzte Richtungen aufweisen. Die Modellierung des Lager-Problems mit Hilfe von disjunktiven Präzedenzbedingungen führt zu disjunktiven Graphen, bei welchen diese Eigenschaft nicht zutrifft. Dies führt zu einer Verallgemeinerung des Konzepts der disjunktiven Graphen. Als neuer Modellierungsansatz werden in dieser Arbeit verallgemeinerte disjunktive Graphen betrachtet, welche sich von klassischen disjunktiven Graphen dadurch unterscheiden, dass die disjunktiven Mengen zwei Bogen mit unterschiedlichen Start- und Endknoten umfassen. Die strukturellen Eigenschaften von verallgemeinerten disjunktiven Graphen werden ausführlich untersucht. Als wichtiges Resultat wird gezeigt, dass das Zulässigkeitsproblem für verallgemeinerte disjunktive Graphen NP-hart ist. Unter dem Zulässigkeitsproblem wird die Frage verstanden, ob ein verallgemeinerter disjunktiver Graph eine zulässige, d.h. eine vollständige, positiv azyklische Selektion von disjunktiven Bogen besitzt. Weiter wird gezeigt, dass diese plexitätstheoretische Eigenschaft auch für die disjunktiven Lager-Graphen zutrifft, welche bei der Modellierung des Lager-Problems resultieren. Dies hat weitreichende Konsequenzen für den Entwurf eines Optimierungsverfahrens für das Lager-Problem. Eine Folge davon ist, dass ein Grossteil der Lösungsansätze, welche im Zusammenhang mit dem Job-Shop-Problem entwickelt wurden, nicht auf das Lager-Problem übertragbar sind. Heuristische Eröffnungsmethoden wie beispielsweise Prioritätsregeln-Verfahren sind kaum anwendbar, da die Frage, ob eine bestehende Teillösung zu einer zulässigen Lösung erweitert werden kann, NP-hart ist. Verbesserungsverfahren, welche auf dem Austausch von kritischen disjunktiven Bogen beruhen, sind ebenfalls problematisch, da der Austausch kritischer Bogen in verallgemeinerten disjunktiven Graphen zu unzulässigen Lösungen führen kann. Bottleneck-Verfahren im Stil des bekannten Shifting-Bottleneck- Algorithmus sind nicht anwendbar, da die Sequenzierung einzelner Prozessoren typischerweise unzulässige Lösungen produziert. Der Entwurf eines geeigneten Nachbarschaftsbegriffs für ein Verbesserungsverfahren erweist sich als schwierig, da im allgemeinen mehrere disjunktive Bogen auf verschiedenen Prozessoren ausgetauscht werden müssen, damit eine zulässige Nachbarlösung resultiert. Beim Entwurf eines Nachbarschaftsbegriffs stellt sich die Frage, welche Bogen beim Austausch eines kritischen Bogens zusätzlich ausgetauscht werden müssen, damit eine zulässige Nachbarselektion entsteht. Zur Bewältigung dieses Problems wird das Konzept der erzwungenen und verbotenen disjunktiven Bogen eingeführt. Ein disjunktiver Bogen heisst erzwungen bzw. verboten von einer Teilselektion, wenn alle zulässigen Selektionen, welche diese Teilselektion umfassen, diesen Bogen enthalten müssen bzw. nicht enthalten können. Zur Lösung des Lager-Problems wird ein Nachbarschaftsbegriff entworfen, welcher einerseits auf dem Konzept der erzwungenen und verbotenen Bogen basiert, und andererseits auf der Idee der 1-Job-Lager-Graphen. Diese bilden eine Relaxation der Lager-Graphen, bei welchen nur disjunktive Bogen betrachtet werden, die mit einem ausgewählten Job inzidieren. Betrachtet werden 1- Job-Lager-Graphen, welche konjunktiv abgeschlossen sind, d.h. in welchen keine disjunktiven Bogen erzwungen werden. Als wichtiges Resultat wird gezeigt, dass ein konjunktiv abgeschlossener, positiv azyklischer 1-Job-Lager-Graph stets eine zulässige Selektion besitzt. Weiter wird gezeigt, dass das Zulässigkeitsproblem für 1-Job-Lager-Graphen polynomial lösbar ist und die Bestimmung der erzwungenen Bogen mit polynomialem Aufwand möglich ist. Diese Resultate ermöglichen den Entwurf eines relativ komplexen Nachbarschaftsbegriffs, bei welchem ausgehend von einem 1-Job-Lager-Graphen durch Bestimmung der erzwungenen Bogen und Ergänzung zu einer zulässigen Selektion eine Nachbarlösung konstruiert wird. Auf der Basis dieses Nachbarschaftsbegriffs wird ein iteratives Abstiegsverfahren entwickelt, welches eine bestehende Lösung sukzessive durch Austausch von kritischen Bogenmengen verbessert. Die numerischen Resultate sind vielversprechend und zeigen ein beträchtliches Optimierungspotential. Für realistische Problemdaten und zufällige Startreihenfolgen wird bei einem Rechenaufwand von wenigen Minuten eine Verbesserung der Ablaufpläne im Bereich von dreissig bis fünfzig Prozent erzielt.
Faculty
Faculté des sciences et de médecine
Department
Département d'Informatique
Language
  • German
Classification
Computer science and technology
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/299724
Statistics
Document views: 247 File downloads:
  • 1_KlinkertA.pdf: 162