BWL, insb. Management Science und Operations Research

This computational study investigates a production scheduling problem for a two-stage hybrid flow shop (HFS) with parallel machines at least at one stage and with zero inter-stage waiting policies between process steps. This scenario is important in industries such as steel production and chemical processing, where cooling time between process steps must be avoided. In this paper, we propose eight dispatching rules that are applied to instances of up to 200 jobs, and benchmark them based on various performance metrics that demonstrate the effectiveness of the proposed heuristic approaches. The dispatching rules, such as Shortest Task Time (STT) and Shortest Processing Time (SPT) are combined with machine assignment rules, such as First Available Machine (FAM) and Minimum Idle Time (MIT), and optimized for makespan and total completion time in the no-wait HFS. Furthermore, for our computational study, we investigate two sequencing approaches - stage-oriented decomposition (A1) and reduction to a flow shop problem (A2) - in the benchmark of this computational study.

Um einen schnellen Zugriff auf die gelagerten Artikel zu gewährleisten, gibt es verschiedene Arten von Lagersystemen. Eine Reihe von Faktoren, darunter die physische Größe und das Gewicht der zu lagernden Artikel, die Nutzungshäufigkeit und die verfügbaren Ressourcen, bestimmen, welcher Systemtyp für ein bestimmtes Lager am besten geeignet ist. In diesem Beitrag soll ein neuer Typ von Lagersystemen untersucht werden: Kompaktlagersysteme. Kompaktlagersysteme zielen darauf ab, eine möglichst hohe Raumausnutzung bei begrenztem Lagerplatz zu erreichen. Zwar ist solch ein Lager platzsparend, allerdings ist die Entnahme von Artikeln aus Kompaktlagersystemen komplex. Durch die dichte Anordnung sind die Ladeeinheiten oft nicht direkt zugänglich, da sie von anderen Einheiten verdeckt werden. Diese müssen erst verschoben oder umpositioniert werden, um genügend Platz für den Zugriff auf das gewünschte Objekt zu schaffen. Dies führt zu komplexen Entscheidungsprozessen. Da das Umpositionieren von Ladeeinheiten Energie verbraucht, trägt eine effiziente Entscheidungsfindung direkt zu einem energieeffizienten Lagersystem bei. Dies erfordert die Entwicklung von algorithmischen Unterstützungssystemen, die in der Lage sind, optimale Entnahmestrategien in angemessener Zeit zu berechnen. In diesem Bericht geben wir einen Überblick über die Annahmen und das strukturelle Optimierungsproblem, das diesen Entnahmestrategien zugrunde liegt. Darüber hinaus bieten wir Einblicke in die Berechenbarkeit und die algorithmischen Ansätze, die zur Ableitung effizienter Lösungen verwendet werden.

Machine scheduling problems can be found in any practical environment from logistics to manufacturing, where tasks, called jobs, are completed by assigning them to resources, called machines. In this thesis, we assume that the execution of jobs deteriorates the machine to the point where it may not be in a state to process further jobs, or, more generally, restricts the availability of the machine. Time is often considered to be the main factor in machine deterioration, such as the time elapsed since the start of planning. However, with regard to practice, there are other important factors besides time that can have a significant impact on the machine state. In this work, we concentrate on factors based on the job positions in the scheduling sequence, summarized as position-dependent machine availability constraints. This characteristic can be found in any production or logistics environment where the assignment of the job to the machine determines the availability of the machine to process jobs, rather than the processing time. First, a definition and the existing literature of the superordinate research field of problems with position-dependent availability is given: state-dependent machine availability. In the following, single machine scheduling problems with position-dependent maintenance or with jobs that have to be sequenced at fixed positions are analyzed regarding their complexity. These assumptions represent specific characteristics of position-dependent availability in scheduling. For each assumption, complexity results are presented for single machine scheduling problems minimizing completion time or due date related objective functions. In addition, polynomial-time algorithms are formulated for specific scheduling problems. Finally, we deal with the hybrid flow shop scheduling (HFS) problem that is characterized by a flow shop layout with at least one stage of processing with parallel machines. Priority rules and constructive heuristics are tested and evaluated on 1260 instances for the two-stage no-wait HFS problem with two identical machines on the first stage and one machine on the second stage, which is known to be NP-hard. Furthermore, HFS problems with unrelated machines are assumed, considering setup times on the machines caused by different job families. Constructive heuristics are tested on 960 instances to study the influence of the number of setups on the results for completion time related objective functions.

We consider a scheduling problem for two gantry cranes moving on the same rails at a single storage block. Containers originating at the seaside have to be stored in the block and containers that are already stored in the storage area at the beginning of the planning horizon have to be delivered to the landside handover point within given time windows. Most commonly in seaport operations, the berthing time of vessels is to be minimized. Thus, the objective considered in this article is to minimize the makespan of seaside container processing while guaranteeing on-time processing of landside containers and while considering non-crossing constraints among cranes. We allow preemption of seaside container processing. This means that one crane may move a seaside container to an intermediate storage slot, and the other crane takes it to its designated position. This has previously been shown to be an effective method of reducing the makespan when compared to classical approaches. We present a dynamic programming (DP) algorithm and a related beam search heuristic. The DP method makes use of bounding techniques and applies dominance properties of optimal solutions. In computational tests, we show that the DP approach clearly outperforms CPLEX and that it is able to quickly solve instances with real-world yard settings. The beam search heuristic is shown to be capable of quickly improving solutions of heuristic approaches that have previously been introduced in the literature. This allows both algorithms to be applied in real-world online settings, where container data is revealed incrementally.

This document presents a simple extension of the TSPLIB file format to serve our needs in the Inventory Routing Problem types. Instead of creating a new file format or putting ASCII files online with a simple description, we have chosen to extend the TSPLIB file format.