go-v.orgdoi

Optimizing the retrieval effort in stack-based storage systems

Sven Boge · osnaDocs (Osnabrück University) · 2022

  • DOI 10.48693/208
  • Publisher Osnabrück University
  • Type dissertation
  • Issued 2022

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

osnaDocs (Osnabrück University) · Osnabrück University · dissertation · 2022

Abstract

In this thesis we investigate three different aspects of stacking problems. In the context of stacking problems, a certain amount of items are usually stored in a limited number of stacks with limited stack height. At first we focus on an elementary loading problem, the parallel stack loading problem (PSLP). We consider the PSLP with the objective to minimize the number of reshuffles in the unloading phase. Since in the PSLP the incoming items have to be stored according to a fixed arrival sequence, some relocations cannot be avoided later on.

In this context, we give a strengthened NP-completeness proof and study the two surrogate objective functions minimizing the total number of unordered stackings of adjacent items and the total number of badly placed items. These objective functions are established in the literature to estimate the number of reshuffles and we compare them theoretically as well as in a computational study with the desired objective function to minimize the number of reshuffles. For this purpose, mixed-integer programming (MIP) formulations and a simulated annealing (SA) algorithm are proposed.

Altogether, it turned out that minimizing the number of reshuffles directly with a two-stage SA approach is superior to the application of exact MIP approaches to the surrogate objective function mentioned above. Furthermore, we consider the premarshalling problem, where items in a storage area have to be sorted for convenient retrieval. A new model for uncertainty is introduced, where the priority values induced by the retrieval sequence of the items are uncertain. We propose a robust optimization approach for this setting, study complexity issues and provide different MIP formulations. Moreover, we investigate helpful properties which can speed up the solution process in several cases.

In a two-stage approach we use the results from the theoretical analysis and MIP formulations to calculate optimal objective values of optimally robust storage configurations in a first step and compute premarshalling solutions with a minimal number of reshuffles to reach optimal configurations in a second step. In a computational study using a wide range of benchmark instances from the literature, we investigate both the efficiency of the approach as well as the benefit and cost of robust solutions.

We find that it is possible to achieve a considerably improved level of robustness by using just a few additional relocations in comparison to solutions which do not take uncertainty into account. Finally, we consider the process of unloading items from a storage in the case of the blocks relocation problem with item families. For a given sequence of families, it has to be decided which item of each demanded family is unloaded from the storage with the objective to minimize the total number of reshuffles. Besides new complexity results, we propose IP formulations and a two-stage SA algorithm.

Computational results are presented for real-world data from a company, benchmark instances from the literature, and randomly generated instances with different characteristics.

Open the resolved locator · 10.48693/208

Metadata licence: OpenAlex metadata (CC0)