Models and optimization techniques for intralogistic problems in part supply

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