TU Darmstadt / ULB / TUbiblio

Integrating Workforce Scheduling Aspects into Daily Operations at Trailer Terminals with a Special Focus on Loading and Unloading of Trucks

Tadumadze, Giorgi (2021)
Integrating Workforce Scheduling Aspects into Daily Operations at Trailer Terminals with a Special Focus on Loading and Unloading of Trucks.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00017583
Dissertation, Erstveröffentlichung, Verlagsversion

Kurzbeschreibung (Abstract)

The cumulative dissertation at hand consists of four research papers, three of which have already been published in scientific journals. The fourth is under review to be published in another international journal. All four articles deal with the combinatorial optimization problems that arise through integrating personnel scheduling factors into operative planning at cargo handling facilities. More precisely, the considered planning problems are related to trucks' unloading and loading processes at massive transshipment terminals, crucial nodes for many modern transportation networks. Examples for such large trailer terminals can be distribution centers or cross-docks (e.g., in the food or automotive industry), hub terminals in the postal sector, etc. At such cargo facilities, hundreds of trucks are coordinated daily. In particular, goods are unloaded from incoming trucks, possibly stored for a while, consolidated, and loaded into outgoing trucks. Typically, a terminal building of such cargo facility consists of several gates (or dock doors), where trucks are docked while goods are unloaded or loaded into the trailer. One crucial planning problem at such facilities is to schedule trucks' loading and unloading processes at the terminal gates. The planning problem that determines on at which door and in which time interval each truck has to be (un-)loaded is called truck scheduling problem.

Although trailers' (un-)loading activities at the gates usually require worker's involvement, the integration of personnel planning aspects into truck scheduling problems has only received little attention in the scientific literature. The focus of this thesis is to integrate workforce planning into truck scheduling problems. The planning problems proposed in the presented articles differ in spatial aspects where the respective operations take place. They include activities at the gates in both the receiving and the shipping areas of the facility as well as activities within the terminal yard, i.e., outside the terminal building. Furthermore, as discussed below, these four papers apply different methodologies to solve the corresponding optimization problems.

The first paper focuses on inbound operations, i.e., in the receiving area of the cargo facility. We introduce a novel integrated workforce and truck scheduling problem, where incoming trucks with strict arrival and departure times are unloaded at the dock doors by a varying number of terminal employees. The duration of the trailer's unloading depends not only on the specific truckload but also on the number of workers jointly unloading it. It is worth mentioning that most existing models widely ignore the latter phenomenon by assuming constant handling times for each truck. That represents the case where a fixed number of employees are preassigned to each dock door in advance. In practice, however, terminal managers have additional flexibility in assigning a diverse number of employees to each truck, depending on the degree of its actual urgency. Since a higher number of employees speeds up the handling time, it is reasonable to solve the personnel assignment and truck scheduling problem holistically. We examine the integrated planning approach for two representative truck scheduling settings: a conventional distribution center and a cross-docking terminal. The resulting two optimization problems differ from each other in their objectives. The former's objective is to minimize the total flow-time (i.e., the total time a truck spends at the terminal, including the waiting time before the actual unloading process). In the cross-docking environment, the goods are directly moved towards the corresponding outbound trucks without any (extended) intermediate storage in the terminal. Hence, the latter problem aims to schedule the incoming trucks at the inbound gates in such a way that the unloaded goods can be transferred to the corresponding outbound trucks on time. More precisely, the truck scheduling problem in the cross-docking setting minimizes the number of delayed shipments that cannot reach the dedicated outbound trucks before the scheduled departure time.

After formalizing the planning problems as mathematical optimization problems, we develop a mixed-integer linear optimization programming model for each setting. Moreover, we provide an alternative problem reformulation as the interval scheduling problem. Based on this, we design various heuristic solution procedures, which are different in terms of the interval generation process in the model preparation phase. We test the algorithmic performance of the proposed solution approaches using newly generated problem instances. Thereby, one of the proposed strategies proves to be very successful, obtaining (near-to-)optimal solutions in a reasonable computational time for the problem instances of realistic size. Furthermore, we compare the novel integrated truck and workforce scheduling approach with existing successive methods that solve the personnel assignment and the truck scheduling problem sequentially. The results show that compared to the existing approaches, the novel integrated planning approach can significantly improve the terminal's performance for both representative settings.

The second article focuses on operations in the shipping area and deals with the loading and scheduling of outbound trucks. More precisely, the planning problem deals with the following decisions: assigning shipments with varying sizes to outgoing trucks considering the trailers' limited loading capacity, and scheduling the trucks' loading processes at the gates considering the given time windows and limited terminal workforce—required to load the shipments into trucks. Such a planning problem arises at cargo facilities where the goods are consolidated on the outbound side. An important example of such facilities is dispatch warehouses of part suppliers (e.g., in the automotive industry), from which multiple trucks depart towards the same destination each day. Such dispatch warehouses are primarily implemented to deliver readily usable parts to the assembly plant in a just-in-time or sometimes even just-in-sequence manner. Therefore, the objective of the proposed optimization problem is to ship the ordered parts as late as possible, but not later than their deadlines at the assembly line.

We formalize the resulting planning problem as a mathematical optimization problem and design two different mixed-integer linear programming models. Furthermore, we reformulate the optimization problem as the well-known generalized set covering problem, which we use as the basis for the column generation method, and design an exact branch-and-price algorithm. In series of numerical tests, we observe the computational performance of the proposed three solution approaches (i.e., two MILP models using the standard solver, and the exact branch-and-price algorithm) on newly generated large problem instances. Our results show that the branch-and-price algorithm outperforms both MILP models, obtaining optimal solutions for most of the considered problem instances in a short computational time. Moreover, we explore some managerial insights, such as the influence of the time window management and workforce amount on delivery punctuality. Our findings can be useful for terminal managers when designing a suitable time window management system or seeking the proper workforce amount at the tactical planning level.

The third article covers the activities within the trailer yard, i.e., outside the terminal building. Many large trailer terminals use specialized yard tractors (often called spotters or switchers) to transport semitrailers within the yard. This way, a new planning problem arises, associated with coordinating the intra-yard trailer movement among multiple spotters. In the third paper, we introduce a novel spotter scheduling problem that has to be solved in the planning hierarchy after defining the particular gate and the docking time for each trailer (i.e., after solving the truck scheduling problem). Our robust spotter scheduling problem assigns a set of given trailer movements to spotters such that the predefined truck schedules can be realized on time—even if unexpected delays occur in the trailer yard. We insert a buffer time between any pair of consecutive transportation requests and aim to keep it as large as possible to protect the system from propagating small delays. We propose two problem variants of the robust spotter scheduling problem, which differ in their objectives. The first problem version maximizes the weighted sum of buffer times (max-sum), and the second one the minimum weighted buffer time (max-min).

For each problem variant, we develop an exact algorithm that finds the optimal solution in polynomial time for the related optimization problem. Our approaches show an outstanding algorithmic performance in computational tests, optimally solving instances with thousands of transport requests and hundreds of spotters in short computational time. Besides, we evaluate the robustness of the proposed approaches in a simulation study. Specifically, we simulate some uncertain events at the terminal, such as delays in truck arrivals and handling processes at the loading gates, and examine whether the solutions found by the proposed approaches are indeed robust. The results show that applying a suitable robustness measure (i.e., max-min) can significantly reduce the propagation of unforeseen delays. Finally, we also observe the interrelation between the two objectives and explore the impact of the spotter fleet size on the yard performance. The latter study's findings can be a useful insight for mid-term planning when seeking an appropriate number of spotters to achieve the desired service level.

In contrast to the three previous papers, each dealing with the specific application problems, the fourth paper primarily focuses on algorithmics. Its main contribution is a novel exact algorithm, based on the combinatorial (or logic-based) Benders decomposition scheme, that can be applied to optimally solve a broader class of scheduling problems. In particular, the fundamental optimization problem is to schedule a set of jobs with release dates and deadlines on a set of unrelated parallel machines minimizing some min-max objective. Such types of machine scheduling problems have a wide range of applications for various scheduling problems in production and logistics, including truck scheduling problems. In the truck scheduling context, a job (with the release date and the deadline) corresponds to a truck (with the arrival and the departure time), and a machine to a gate that can process at most one job at a time. Apart from the exact Benders decomposition algorithm, we propose a heuristic algorithm that relies on a reformulation of the optimization problem as the well-known generalized set partitioning problem. We design the algorithms for three different minimax objective functions: minimizing the completion time of the last job (i.e., makespan), the maximum weighted flow time, and the maximum weighted lateness. Besides, we reveal how to modify the proposed algorithms for several problem-relevant extensions. We test the computational performance of the provided solution techniques in an extensive computational study on both newly generated random problem instances and existing instance sets available in the literature. The novel exact Benders decomposition approach performs quite well, solving most problem instances to proven optimality within short computational time. The proposed heuristic also does a good job, successfully providing near-optimal solutions in a reasonable time for particularly tricky problem instances with tight time windows.

Typ des Eintrags: Dissertation
Erschienen: 2021
Autor(en): Tadumadze, Giorgi
Art des Eintrags: Erstveröffentlichung
Titel: Integrating Workforce Scheduling Aspects into Daily Operations at Trailer Terminals with a Special Focus on Loading and Unloading of Trucks
Sprache: Englisch
Referenten: Emde, Prof. Dr. Simon ; Glock, Prof. Dr. Christoph
Publikationsjahr: 2021
Ort: Darmstadt
Kollation: xx, 187 Seiten
Datum der mündlichen Prüfung: 15 Dezember 2020
DOI: 10.26083/tuprints-00017583
URL / URN: https://tuprints.ulb.tu-darmstadt.de/17583
Kurzbeschreibung (Abstract):

The cumulative dissertation at hand consists of four research papers, three of which have already been published in scientific journals. The fourth is under review to be published in another international journal. All four articles deal with the combinatorial optimization problems that arise through integrating personnel scheduling factors into operative planning at cargo handling facilities. More precisely, the considered planning problems are related to trucks' unloading and loading processes at massive transshipment terminals, crucial nodes for many modern transportation networks. Examples for such large trailer terminals can be distribution centers or cross-docks (e.g., in the food or automotive industry), hub terminals in the postal sector, etc. At such cargo facilities, hundreds of trucks are coordinated daily. In particular, goods are unloaded from incoming trucks, possibly stored for a while, consolidated, and loaded into outgoing trucks. Typically, a terminal building of such cargo facility consists of several gates (or dock doors), where trucks are docked while goods are unloaded or loaded into the trailer. One crucial planning problem at such facilities is to schedule trucks' loading and unloading processes at the terminal gates. The planning problem that determines on at which door and in which time interval each truck has to be (un-)loaded is called truck scheduling problem.

Although trailers' (un-)loading activities at the gates usually require worker's involvement, the integration of personnel planning aspects into truck scheduling problems has only received little attention in the scientific literature. The focus of this thesis is to integrate workforce planning into truck scheduling problems. The planning problems proposed in the presented articles differ in spatial aspects where the respective operations take place. They include activities at the gates in both the receiving and the shipping areas of the facility as well as activities within the terminal yard, i.e., outside the terminal building. Furthermore, as discussed below, these four papers apply different methodologies to solve the corresponding optimization problems.

The first paper focuses on inbound operations, i.e., in the receiving area of the cargo facility. We introduce a novel integrated workforce and truck scheduling problem, where incoming trucks with strict arrival and departure times are unloaded at the dock doors by a varying number of terminal employees. The duration of the trailer's unloading depends not only on the specific truckload but also on the number of workers jointly unloading it. It is worth mentioning that most existing models widely ignore the latter phenomenon by assuming constant handling times for each truck. That represents the case where a fixed number of employees are preassigned to each dock door in advance. In practice, however, terminal managers have additional flexibility in assigning a diverse number of employees to each truck, depending on the degree of its actual urgency. Since a higher number of employees speeds up the handling time, it is reasonable to solve the personnel assignment and truck scheduling problem holistically. We examine the integrated planning approach for two representative truck scheduling settings: a conventional distribution center and a cross-docking terminal. The resulting two optimization problems differ from each other in their objectives. The former's objective is to minimize the total flow-time (i.e., the total time a truck spends at the terminal, including the waiting time before the actual unloading process). In the cross-docking environment, the goods are directly moved towards the corresponding outbound trucks without any (extended) intermediate storage in the terminal. Hence, the latter problem aims to schedule the incoming trucks at the inbound gates in such a way that the unloaded goods can be transferred to the corresponding outbound trucks on time. More precisely, the truck scheduling problem in the cross-docking setting minimizes the number of delayed shipments that cannot reach the dedicated outbound trucks before the scheduled departure time.

After formalizing the planning problems as mathematical optimization problems, we develop a mixed-integer linear optimization programming model for each setting. Moreover, we provide an alternative problem reformulation as the interval scheduling problem. Based on this, we design various heuristic solution procedures, which are different in terms of the interval generation process in the model preparation phase. We test the algorithmic performance of the proposed solution approaches using newly generated problem instances. Thereby, one of the proposed strategies proves to be very successful, obtaining (near-to-)optimal solutions in a reasonable computational time for the problem instances of realistic size. Furthermore, we compare the novel integrated truck and workforce scheduling approach with existing successive methods that solve the personnel assignment and the truck scheduling problem sequentially. The results show that compared to the existing approaches, the novel integrated planning approach can significantly improve the terminal's performance for both representative settings.

The second article focuses on operations in the shipping area and deals with the loading and scheduling of outbound trucks. More precisely, the planning problem deals with the following decisions: assigning shipments with varying sizes to outgoing trucks considering the trailers' limited loading capacity, and scheduling the trucks' loading processes at the gates considering the given time windows and limited terminal workforce—required to load the shipments into trucks. Such a planning problem arises at cargo facilities where the goods are consolidated on the outbound side. An important example of such facilities is dispatch warehouses of part suppliers (e.g., in the automotive industry), from which multiple trucks depart towards the same destination each day. Such dispatch warehouses are primarily implemented to deliver readily usable parts to the assembly plant in a just-in-time or sometimes even just-in-sequence manner. Therefore, the objective of the proposed optimization problem is to ship the ordered parts as late as possible, but not later than their deadlines at the assembly line.

We formalize the resulting planning problem as a mathematical optimization problem and design two different mixed-integer linear programming models. Furthermore, we reformulate the optimization problem as the well-known generalized set covering problem, which we use as the basis for the column generation method, and design an exact branch-and-price algorithm. In series of numerical tests, we observe the computational performance of the proposed three solution approaches (i.e., two MILP models using the standard solver, and the exact branch-and-price algorithm) on newly generated large problem instances. Our results show that the branch-and-price algorithm outperforms both MILP models, obtaining optimal solutions for most of the considered problem instances in a short computational time. Moreover, we explore some managerial insights, such as the influence of the time window management and workforce amount on delivery punctuality. Our findings can be useful for terminal managers when designing a suitable time window management system or seeking the proper workforce amount at the tactical planning level.

The third article covers the activities within the trailer yard, i.e., outside the terminal building. Many large trailer terminals use specialized yard tractors (often called spotters or switchers) to transport semitrailers within the yard. This way, a new planning problem arises, associated with coordinating the intra-yard trailer movement among multiple spotters. In the third paper, we introduce a novel spotter scheduling problem that has to be solved in the planning hierarchy after defining the particular gate and the docking time for each trailer (i.e., after solving the truck scheduling problem). Our robust spotter scheduling problem assigns a set of given trailer movements to spotters such that the predefined truck schedules can be realized on time—even if unexpected delays occur in the trailer yard. We insert a buffer time between any pair of consecutive transportation requests and aim to keep it as large as possible to protect the system from propagating small delays. We propose two problem variants of the robust spotter scheduling problem, which differ in their objectives. The first problem version maximizes the weighted sum of buffer times (max-sum), and the second one the minimum weighted buffer time (max-min).

For each problem variant, we develop an exact algorithm that finds the optimal solution in polynomial time for the related optimization problem. Our approaches show an outstanding algorithmic performance in computational tests, optimally solving instances with thousands of transport requests and hundreds of spotters in short computational time. Besides, we evaluate the robustness of the proposed approaches in a simulation study. Specifically, we simulate some uncertain events at the terminal, such as delays in truck arrivals and handling processes at the loading gates, and examine whether the solutions found by the proposed approaches are indeed robust. The results show that applying a suitable robustness measure (i.e., max-min) can significantly reduce the propagation of unforeseen delays. Finally, we also observe the interrelation between the two objectives and explore the impact of the spotter fleet size on the yard performance. The latter study's findings can be a useful insight for mid-term planning when seeking an appropriate number of spotters to achieve the desired service level.

In contrast to the three previous papers, each dealing with the specific application problems, the fourth paper primarily focuses on algorithmics. Its main contribution is a novel exact algorithm, based on the combinatorial (or logic-based) Benders decomposition scheme, that can be applied to optimally solve a broader class of scheduling problems. In particular, the fundamental optimization problem is to schedule a set of jobs with release dates and deadlines on a set of unrelated parallel machines minimizing some min-max objective. Such types of machine scheduling problems have a wide range of applications for various scheduling problems in production and logistics, including truck scheduling problems. In the truck scheduling context, a job (with the release date and the deadline) corresponds to a truck (with the arrival and the departure time), and a machine to a gate that can process at most one job at a time. Apart from the exact Benders decomposition algorithm, we propose a heuristic algorithm that relies on a reformulation of the optimization problem as the well-known generalized set partitioning problem. We design the algorithms for three different minimax objective functions: minimizing the completion time of the last job (i.e., makespan), the maximum weighted flow time, and the maximum weighted lateness. Besides, we reveal how to modify the proposed algorithms for several problem-relevant extensions. We test the computational performance of the provided solution techniques in an extensive computational study on both newly generated random problem instances and existing instance sets available in the literature. The novel exact Benders decomposition approach performs quite well, solving most problem instances to proven optimality within short computational time. The proposed heuristic also does a good job, successfully providing near-optimal solutions in a reasonable time for particularly tricky problem instances with tight time windows.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

Die vorliegende kumulative Dissertation besteht aus vier wissenschaftlichen Artikeln, von denen drei bereits in wissenschaftlichen Zeitschriften veröffentlicht wurden und einer sich in dem Begutachtungsprozess für Veröffentlichung in einer weiteren internationalen Fachzeitschrift befindet. Alle vier Artikel beschäftigen sich mit den kombinatorischen Optimierungsproblemen, die durch Integration der Personalfaktoren in verschiedenen operativen Planungsproblemen im Bereich der Umschlaglogistik entstehen. Insbesondere sind alle betrachteten Planungsprobleme mit Ent- und Beladeprozessen der Lastkraftwagen (LKWs) an riesigen Umschlagterminals verbunden, die wichtige Knotenpunkte für viele moderne Distributionsnetzwerke darstellen. Typischerweise werden an solchen riesigen Umschlagterminals täglich hunderte LKWs koordiniert, indem die Güter von ankommenden LKWs entladen, umsortiert, möglicherweise zwischengelagert und in ausgehende LKWs geladen werden. Dabei verfügt ein Terminalgebäude i. d. R. über mehrere Ladetore, an denen LKWs angedockt werden, während die Waren aus einem Anhänger eines einkommenden LKWs entladen bzw. in einen Anhänger eines ausgehenden LKWs geladen werden. Beispiele für solche Umschlagterminals sind große Distributionszentren oder sogenannte Cross-Docks (z. B. in der Lebensmittel- oder Automobilindustrie), Hub-Terminals in der Postindustrie usw. Eines der am intensivsten untersuchten Probleme bei der Betriebsplanung solcher Umschlagterminals bezeichnet man als Truck Scheduling Problem, welches die LKWs den Toren und jeweiligen Abfertigungszeitfenstern zuweist.

Obwohl die Ent- und Beladevorgänge an den Laderampen i. d. R. eine Beteiligung menschlicher Arbeitskräfte voraussetzen, hat die Berücksichtigung der Personalplanungsaspekte in den Truck Scheduling Problemen bisher nur geringe Aufmerksamkeit in der wissenschaftlichen Literatur gefunden. Der Schwerpunkt dieser Dissertation liegt auf der Integration der Personalaspekte in Truck Scheduling Probleme. Die in unterschiedlichen Artikeln vorgestellten Optimierungsprobleme unterscheiden sich in räumlichen Aspekten, d. h. in den Örtlichkeiten im Umschlagterminal, in denen die jeweiligen Aktivitäten stattfinden. Sie umfassen Aktivitäten an den Laderampen sowohl im Wareneingang als auch im Warenausgang sowie Vorgänge innerhalb des Hofs des Terminals (d. h. außerhalb des Terminalgebäudes). Darüber hinaus unterscheiden sich die vier Aufsätze auch im Hinblick auf die Methoden, die zur Lösung der Planungsprobleme eingesetzt werden.

Das in dem ersten Artikel betrachtete Planungsproblem beschäftigt sich mit dem Truck Scheduling Problem im Wareneingang. Insbesondere wird ein neuartiges integriertes Personal- und LKW-Planungsproblem untersucht, in dem ankommende LKWs mit beschränkten Zeitfenstern (definiert durch fixe Ankunfts- und Abfahrtszeiten) an Terminaltoren von einer variierenden Anzahl an Logistikmitarbeitern entladen werden können. Dabei hängt die Dauer eines Entladevorgangs nicht nur von der spezifischen LKW-Ladung ab, sondern auch von der Anzahl der Mitarbeiter, die die Waren aus dem LKW-Anhänger gemeinsam entladen. Der Großteil bestehender Ansätze in der Literatur ignoriert Personalplanungsaspekte in dem Truck Scheduling Problem; es wird von festen Abfertigungszeiten für jeden LKW ausgegangen und somit angenommen, dass jeder Laderampe eine feste Anzahl an Mitarbeitern im Voraus zugewiesen wird. Es besteht jedoch ein zusätzlicher Freiheitsgrad darin, je nach Dringlichkeit dem jeweiligen Ladevorgang eine variierende Anzahl der Mitarbeiter zuzuordnen. Eine höhere Anzahl von Mitarbeitern beschleunigt die Abfertigung des Vorganges, sodass es sinnvoll ist, Personal-Zuordnung und Truck Scheduling Problem ganzheitlich zu lösen. Das sich daraus ergebende ganzheitliche Planungsproblem wird für zwei repräsentative Anwendungsfälle des Truck Scheduling Problems untersucht: für ein konventionelles Distributionszentrum und für eine Cross-Dock Umgebung, die sich voneinander in ihren Zielsetzungen unterscheiden. Bei Distributionszentren ist die Zielsetzung des betrachteten Optimierungsproblems, die gesamte Flow-Time (d. h. die gesamte Zeit, die ein LKW am Terminal verbringt, inklusive der Wartezeit vor dem tatsächlichen Entladevorgang) zu minimieren. Im Kontrast dazu versucht das Optimierungsproblem in der Cross-Docking Umgebung, die ankommenden LKWs an den Entladetoren so zu planen, dass die entladene Ware in entsprechende ausgehende LKWs möglichst termingerecht umgeladen wird.

Nach der formellen Darstellung der entstandenen Planungsprobleme wird für jede Problemvariante ein gemischt-ganzzahliges lineares Optimierungsmodell entwickelt. Darüber hinaus werden die Optimierungsprobleme als sogenanntes Intervall Scheduling Problem umformuliert und darauf basierend unterschiedliche heuristische Lösungsverfahren entworfen, die sich in der Erzeugung der Intervalle in der Modellaufbereitungsphase unterscheiden. In einer rechnergestützten Studie wird die Rechenleistung der vorgeschlagenen Lösungsansätze auf zufällig generierten Probleminstanzen getestet. Dabei erweist sich eines der Verfahren zur Intervallerzeugung als sehr erfolgreich, welches Probleminstanzen mit realistischen Größenordnungen in angemessener Zeit erfolgreich löst. Des Weiteren wird der neuartige kombinierte Ansatz der Personal- und LKW-Planung mit bestehenden sukzessiven Ansätzen verglichen, in denen die Personal-Zuordnung und das Truck Scheduling nacheinander separat gelöst werden. Die Ergebnisse zeigen, dass im Vergleich zum sukzessiven Ansatz der kombinierte Personalplanungsansatz die Leistung des Truck Scheduling Problems für beide repräsentativen Anwendungsfälle erheblich verbessert.

Der Fokus des zweiten Artikels liegt auf den Aktivitäten im Warenausgang und beschäftigt sich mit der Beladung und Ablaufplanung ausgehender LKWs. Insbesondere befasst sich das in dem zweiten Aufsatz vorgestellte Planungsproblem mit folgenden Entscheidungen: Zum einen müssen die Sendungen mit variierender Größe in die ausgehenden LKWs so verladen werden, dass die begrenzte Kapazität der jeweiligen LKW-Anhänger nicht überschritten wird (LKW-Verladeproblem); zum anderen sind die einzelnen LKWs mit gewissen Ankunft- und Abfahrtzeiten zu den Ladetoren so zu planen, dass begrenzte Terminalressourcen für Ladevorgänge (Ladetore und menschlichen Arbeitskräfte) in Betracht gezogen werden (Truck Scheduling Problem). Ein solches Planungsproblem entsteht typischerweise im Tagesgeschäft der Versandlager in der Produktionsindustrie (z. B. in der Automobilindustrie), da von solchen Versandlagern jeden Tag mehrere Lastwagen in Richtung desselben Zielortes abfahren. Deshalb muss neben dem eigentlichen Truck Scheduling Problem eine Entscheidung darüber getroffen werden, welche Ladeeinheiten in welche LKWs geladen werden. In diesem Umfeld besteht der Hauptzweck solcher Versandlager darin, eine Just-in-Time oder manchmal sogar Just-in-Sequence Lieferung der fertigen Montageteile an die Produktionslinie zu ermöglichen. Daher ist die Zielsetzung des vorgeschlagenen Optimierungsproblems, die bestellten Ladeeinheiten möglichst spät, aber nicht später als zur angeforderten Zeit zu versenden.

Das entstandene Planungsproblem wird als mathematisches Optimierungsproblem formalisiert, für welches zwei verschiedene gemischt-ganzzahlige lineare Optimierungsmodelle entworfen werden. Des Weiteren wird das Optimierungsproblem als bekanntes generalisiertes Set Covering Problem umformuliert, welches als Grundlage der Spaltengenerierung für einen entworfenen exakten Branch-and-Price Algorithmus dient. In einer Reihe von numerischen Tests wird die algorithmische Leistung der vorgeschlagenen Lösungsverfahren mit neu generierten Probleminstanzen getestet und miteinander verglichen. Dabei zeigt der neuartige exakte Branch-and-Price Algorithmus eine hervorragende Leistung und ist den beiden gemischt-ganzzahligen linearen Optimierungsmodellen unter Verwendung eines kommerziellen Standardsolvers überlegen, da er in der Lage ist, den Großteil der betrachteten Probleminstanzen in kurzer Zeit exakt zu lösen. Darüber hinaus werden einige betriebswirtschaftliche Erkenntnisse untersucht, etwa der Einfluss von Zeitfenstermanagement und Personalbestand auf die Pünktlichkeit der Lieferungen, welche als Grundlage für die mittelfristige Planung eines geeigneten Zeitfenstermanagements und Personalbestands genutzt werden können.

Der dritte Artikel beschäftigt sich mit Aktivitäten auf dem Hof eines Trailer-Terminals, d. h. außerhalb des Terminalgebäudes. Auf viele große Umschlagterminals werden die LKW-Sattelanhänger innerhalb des Hofs von speziellen Terminaltraktoren transportiert (in der englischsprachigen Literatur ist so ein Terminaltraktor oft unter dem Namen Spotter bekannt). Dadurch entsteht ein neues Planungsproblem, nämlich die Bewegung der LKW-Anhänger innerhalb des Hofs unter mehreren Spottern effizient zu koordinieren. Im dritten Artikel wird ein neuartiges Planungsproblem von Spottern betrachtet, welches in der Planungshierarchie nach der Festlegung der Ablaufpläne einzelner LKWs an den Toren (Truck Scheduling) gelöst werden muss. Eine Reihe von gegebenen Transportaufträgen ist zu einzelnen Spottern so zuzuordnen, dass gegebene LKW-Pläne zeitlich realisiert werden können. Dabei ist die Zielsetzung des betrachteten Optimierungsproblems, einen möglichst robusten Ablaufplan von Spottern zu finden, der die zeitliche Realisierung der geplanten LKW-Ladungen an den Toren auch dann ermöglicht, wenn unerwartete Verspätungen im ursprünglichen LKW-Plan entstehen. Dafür wird zwischen jedem Paar aufeinanderfolgender Transportaufträge eine Pufferzeit eingesetzt, welche möglichst groß zu halten ist, um das System vor einer Ausbreitung kleiner Verspätungen zu schützen. Es werden zwei Problemvarianten von robuster Spotter-Planung betrachtet, die sich in ihrer Zielsetzung unterscheiden. Die erste Problemvariante zielt darauf, die gewichtete Summe aller Pufferzeiten zu maximieren, wohingegen die Zielsetzung der zweiten Problemvariante die Maximierung der minimalen gewichteten Pufferzeit ist.

Für jede der beiden Problemvarianten wird ein exakter Algorithmus entworfen, welcher das entsprechende Optimierungsproblem in polynomieller Zeit optimal lösen kann. In einer Reihe an Rechenstudien erbringen beide Lösungsansätze eine sehr gute algorithmische Leistung, sodass Instanzen mit tausenden von Transportaufträgen und hunderten von Spottern in wenigen Minuten optimal gelöst werden. Darüber hinaus wird die Robustheit der vorgeschlagenen Ansätze in einer Simulationsstudie evaluiert, in der gewisse Verspätungen der LKW-Ankünfte sowie Verzögerungen von deren Ladevorgängen an den Ladetoren simuliert werden, um zu untersuchen, ob die gefundenen Lösungen tatsächlich robust gegenüber solchen Verspätungen sind. Die Ergebnisse der Simulationsstudie zeigen, dass die Anwendung eines geeigneten Robustheitsmaßes die Ausbreitung unvorhergesehener Verzögerungen erheblich reduzieren kann. Des Weiteren wird der Einfluss der Spotter-Flottengröße auf die Leistung des Hofs untersucht. Die Ergebnisse können als Grundlage für ein mittelfristiges Planungsproblem genutzt werden, in dem ein gewisses Serviceniveau zu erreichen ist und dafür nach einer optimalen Anzahl an Spottern gesucht wird.

Im Unterschied zu den drei vorherigen Artikeln, die jeweils konkrete Anwendungsprobleme in Betracht ziehen, liegt der Schwerpunkt des vierten Artikels eher in der Algorithmik. So ist der Hauptbeitrag des vierten Artikels der Entwurf eines neuartigen exakten Algorithmus, welcher auf dem sogenannten Ansatz der kombinatorischen (oder logic-based) Benders Dekomposition basiert und zur optimalen Lösung einer allgemeineren Klasse der Maschinenplanungsprobleme angewendet werden kann. Insbesondere besteht das grundlegende Optimierungsproblem darin, eine Reihe von Aufträgen (Jobs) mit beschränkten Zeitfenstern auf eine Menge nicht zusammenhängender paralleler Maschinen zu planen und dabei eine gewisse Minimax-Zielfunktion zu minimieren. Solche Arten von Maschinenplanungsproblemen haben eine breite Anwendung für verschiedene Planungsprobleme in der Produktion und Logistik, unter anderem auch für Truck Scheduling Probleme. In diesem Zusammenhang ist ein LKW (mit Ankunfts- und Abfahrtszeit) einem Job (mit Fertigstellungs- und Fälligkeitszeit) gleichzusetzen und ein Ladetor einer Maschine, welche zu jedem Zeitpunkt höchstens einen Job verarbeiten kann. Neben dem exakten Benders Dekomposition Algorithmus wird auch ein heuristisches Lösungsverfahren entworfen, welches auf der Umformulierung des Optimierungsproblems als bekanntes generalisiertes Set Partitioning Problem basiert. Beide entwickelten Algorithmen werden für drei unterschiedliche Minimax-Zielfunktionen entworfen, nämlich für die Minimierung der Fertigstellungszeit des letzten Jobs (d. h. makespan), der größten gewichteten Abfertigungszeit (d. h. maximal weighted flow time) und der größten gewichteten Verspätung (d. h. maximal weighted lateness). Darüber hinaus werden sie für eine Reihe von problemrelevanten Erweiterungen angepasst. Die algorithmische Leistung der neuartigen exakten und heuristischen Lösungsansätze wird in einer umfangreichen rechnerischen Studie sowohl auf neu generierten Probleminstanzen als auch in der Literatur existierenden Datensätzen getestet. Der Benders-Dekomposition-Ansatz schneidet ziemlich gut ab, da er die meisten Probleminstanzen innerhalb kurzer Rechenzeit optimal löst. Auch die Heuristik leistet eine gute Arbeit, insbesondere während der Lösung der schwierigen Instanzen mit engen Zeitfenstern der Jobs.

Deutsch
Status: Verlagsversion
URN: urn:nbn:de:tuda-tuprints-175832
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
300 Sozialwissenschaften > 330 Wirtschaft
500 Naturwissenschaften und Mathematik > 510 Mathematik
Fachbereich(e)/-gebiet(e): 01 Fachbereich Rechts- und Wirtschaftswissenschaften > Betriebswirtschaftliche Fachgebiete > Fachgebiet Management Science / Operations Research
01 Fachbereich Rechts- und Wirtschaftswissenschaften
01 Fachbereich Rechts- und Wirtschaftswissenschaften > Betriebswirtschaftliche Fachgebiete
Hinterlegungsdatum: 24 Mär 2021 07:17
Letzte Änderung: 29 Mär 2021 09:14
PPN:
Referenten: Emde, Prof. Dr. Simon ; Glock, Prof. Dr. Christoph
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 15 Dezember 2020
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen