Anja Heßler

Abstract

In warehouse design, decisions have to be made with respect to the storage location policy, the sizing and allocation of storage capacities, the warehouse layout, the storage and retrieval strategy, and the nominal throughput capacity of the storage and retrieval system. These attributes mainly determine the storage efficiency and the maximum system throughput of the warehouse. A storage location policy like dedicated, class-based dedicated, or random storage establishes the general principle under which storage bins can be assigned to stock keeping units. For a given storage location policy, capacity sizing and allocation fixes the total storage capacity of the warehouse and assigns a set of feasible storage bins to each stock keeping unit. When layouting the warehouse, each storage bin is assigned to a physical storage location and the positions of the input/output points are determined. The storage and retrieval strategy defines the way in which storage and retrieval orders are executed during warehouse operation. Given a set of orders to be processed, the strategy allocates appropriate storage locations to each order and partitions the order set into operation cycles of the storage and retrieval system. The storage efficiency of the system can be specified in terms of the required total storage capacity needed to achieve a given storage service level or in terms of the storage service level that can be guaranteed with a given total storage capacity. The efficiency depends on the storage location policy and the sizing and allocation of the storage capacities. The maximum system throughput can be calculated based on the expected operation cycle time, which for given storage location strategy and layout is mainly influenced by the storage and retrieval strategy and the nominal throughput capacity.

This PhD project is concerned with stochastic models for the design of storage systems. In particular, we develop

• chance-constrained mathematical programming formulations and solution methods for different variants of capacity sizing and allocation problems and
• Markov models for estimating the maximum system throughput under different storage and retrieval strategies.

Capacity sizing and allocation models

The capacity sizing and allocation problem in warehouse design consists in optimizing the rapport between storage service level and total storage capacity by appropriately distributing the storage capacity among individual or classes of stock keeping units. The total, partial, or specific storage service levels are defined as the probabilities that in the steady-state system there remains sufficient storage capacity to execute any, the next, or a specific storage order, respectively. Minimizing the total storage capacity and maximizing a storage service level are conflicting objectives. Hence, capacity sizing and allocation can be interpreted as a bi-criteria optimization problem, for which according to an aspiration level approach two single-objective problems can be considered:

• minimize the total storage capacity required to ensure a given storage service level (primal problem) or
• maximize the storage service level for a given total storage capacity (dual problem).

Efficient solution procedures for the primal or the dual problem can serve as a starting point to algorithms for approximating the Pareto front of the bi-criteria problem.

Assuming storage capacity requirements of the stock keeping units being independent and continuous random variables, the single-objective problems can be formulated as basic nonlinear programs. For dedicated storage and strictly log-concavely distributed capacity requirements, using a KKT approach sufficient and necessary optimality conditions can be reduced to a nonlinear equation, which possesses a unique solution and can be solved efficiently with standard root-finding algorithms.

Markov models for system throughput analysis

Appropriately dimensioning the storage and retrieval system presupposes an accurate model of the system throughput under steady-state conditions. The expected maximum system throughput is the reciprocal of the expected operation cycle time, which is largely influenced by the storage and retrieval strategy. Disregarding the time savings achieved by optimally assigning storage locations to storage and retrieval orders may heavily bias the throughput analysis. Nevertheless, basic approaches to throughput analysis implicitly assume non-optimized, random allocations.

Based on continuous-time Markov chains we derive analytical results for the expected operation cycle time of storage and retrieval systems. In a first setting, we assume homogeneous stock keeping units and consider a rack storage under random storage location strategy serviced by one rack feeder performing single command cycles. We assume that storage and retrieval orders for loading units are released according to independent Poisson arrivals. A system state is identified with the occupancy of the storage locations with stock keeping units. The optimized assignment of storage locations to the orders serviced by the feeder is taken into account by sorting the storage locations with respect to the resulting cycle times and specifying the state transitions in such a way that for the next order to be processed always the first feasible location in this sequence is chosen. For small dimensions, the equilibrium equations for the stationary state probabilities can be solved with standard algorithms for linear equation systems. An analytical formula for the expected cycle time results from constructing aggregate birth-death processes where for fixed parameter n, a system state is identified with the number of occupied storage locations among the first n locations. Comparing the resulting cycle times to guesstimates which can be found in technical guidelines reveals that the latter approximations significantly underestimate the maximum system throughput. Further research will be devoted to generalizing the basic setting to heterogeneous stock keeping units, dual command cycles, and batch arrivals.