1 Introduction

Online retailers from the business-to-consumer (B2C) segment face the following challenges when setting up their order fulfillment processes. Typically, they have to process

  • many orders (e.g., in 2016, global e-retail sales grew 23.7% compared to the previous year, making up 8.7% of the total retail market worldwide, see Statista 2017),

  • with few demanded items (e.g., the average number of demanded items at online retailer Amazon is just 1.6 items per order, see Weidinger and Boysen 2017),

  • from a large assortment (e.g., due to the lower costs many online retailers have a much larger assortment than traditional brick-and-mortar stores; this phenomenon is known as the long-tail of e-commerce, see Brynjolfsson et al. 2003),

  • under great time pressure (e.g., many online retailers offer their customers next- or even same-day deliveries, see Yaman et al. 2012).

Many online retailers, therefore, apply a batching and/or zoning strategy to speed up their picker-to-parts based order fulfilment processes (see de Koster et al. 2007):

  • Batching Instead of returning to the central depot each time a picking order is completed, multiple orders are unified to a batch of orders jointly assembled on a picker tour. This way, the pick density per tour is increased and a more efficient picking process is enabled.

  • Zoning A further reduction of the picking effort is enabled, if the warehouse is partitioned into disjoint zones. Order pickers only pick the part of an order that is stored in their assigned zone. In this way, parallel order picking is enabled and each picker only traverses smaller areas of the warehouse.

On the negative side, batching and/or zoning require a subsequent consolidation process, where the picking orders are unified. Batched orders need to be separated and zoning requires the merging of multiple partial orders picked in different zones. There exist fully automated solutions for the consolidation process based on sortation conveyors (Gallien and Weber 2010; Boysen et al. 2016). Many online retailers, however, aim to avoid the high investment costs for these automated solutions, which are, furthermore, hardly scalable in times of varying workloads. Therefore, many retailers apply manual consolidation processes based on put walls. For instance, we are aware of an order consolidation with put walls in warehouses of Amazon Europe (e.g., in Poznań, Poland, and Bad Hersfeld, Germany) and of European fashion retailer Zalando (e.g., in Erfurt, Germany). However, since many warehouses orientate their processes on these market leaders, put walls should be applied in many more warehouses especially of online retailers.

1.1 Order consolidation with put walls

The fulfillment process of online retailers applying put walls can be differentiated into the following three basic steps:

  1. (i)

    order picking in a batching and/or zoning environment,

  2. (ii)

    intermediate storage of bins, and

  3. (iii)

    order consolidation and packing of orders.

First, the items demanded by customer orders need to be picked [process step (i)]. Most online retailers apply a picker-to-parts order picking in a batching and zoning environment where, additionally, a mixed-shelves policy (also denoted as scattered storage, see Weidinger and Boysen 2017) is applied. Under this policy unit loads of stock keeping units (SKUs) are purposefully broken down and single items are scattered all over the shelves of a warehouse. In this way, there is always some item of a demanded SKU close by irrespective of the current picker location. In such a setting, large online retailers apply dozens of pickers, which are typically assigned to specific zones of the warehouse. They pick batched orders in parallel into bins each finally containing partial orders for multiple customers.

Completed bins are handed over to the central conveyor system. Typically, each bin is not directly released into the consolidation area, but intermediately stored somewhere in the conveyor system [process step (ii)]. Especially in large warehouses, the time span between completion of the first and last bin of a batch may become large. For instance, inventory differences or misplaced items can occur, so that some parts of a batch arrive considerably delayed. If the bins of such a batch would directly be released into the consolidation area, then, at least some positions where orders are collected, i.e., some dead-end lane of a conveyor-based sorting system or the shelves of a put wall, would be blocked for a prolonged time span until the delayed bins arrive. To avoid the excessive consolidation capacity required by a direct bin release, bins are typically collected in the central conveyor system and only released into the consolidation area once the batch is completed. Automated (i.e., conveyor-based) consolidation systems often apply a closed-loop conveyor where items circulate until the complete batch has arrived in the loop (Meller 1997; Johnson 1998). A loop conveyor for a huge number of orders, however, requires excessive space on the shop floor. Therefore, especially large-sized facilities rather apply automated storage and retrieval systems (ASRS), e.g., a crane-operated high-bay rack (Boysen and Stephan 2016) or a carousel rack (Litvak and Vlasiou 2010), to intermediately store bins in a more space-efficient manner.

Fig. 1
figure 1

Schematic layout of the consolidation and packing area

Full size image

The basic layout of a consolidation and packing area applying a put wall [process step (iii)] is schematically depicted in Fig. 1. The bins of a batch released from intermediate storage successively arrive in the consolidation area. At the end of a conveyor segment, a logistics worker we call the putter resides. The putter successively removes the items from the current bin and puts them into the put wall. The put wall is a simple reach-trough rack separated into multiple shelves, which are accessible from both sides. Each shelf is temporarily assigned to a separate order and once the putter scans the current item a put-to-light mechanism indicates into which shelf the current item is to be put. In this way, bin after bin is sorted into the wall. On the other side of the wall reside the packers. Here, another put-to-light mechanism indicates completed orders, so that a packer can empty an indicated shelf and pack the respective items into a cardboard box. Packed orders are, finally, handed over to another conveyor system bringing them towards the shipping area.

Manual order consolidation with put walls is, for instance, applied in the Poznan (Poland) facility of Amazon and we have also seen their application at online retailer Zalando in Erfurt (Germany). Low-tech solutions like put walls do not require large investment costs and are easily adaptable to varying capacity situations. Therefore, put walls are applied by many other online retailers too.

In the following section, the basic decision problems to be solved when operating such a fulfilment process and the related literature treating these problems are described.

1.2 Decision problems and literature review

A vast body of literature has accumulated on warehousing in the recent decades. Instead of trying to summarize all these approaches we refer to the in-depth review papers provided by Gu et al. (2007), Gu et al. (2010) and de Koster et al. (2007). We concentrate our literature survey on the three process steps elaborated in Sect. 1.1.

Existing research on batching and zoning [process step (i)] mainly focuses the impact of both policies on the travel distances of pickers. In-depth surveys on these research efforts are provided by de Koster et al. (2007) and Henn et al. (2012). In our research, we presuppose that all batching and zoning decisions have already been made. A picked batch of bins is assumed to wait in intermediate storage to be released from the ASRS towards the consolidation area.

Not much work is dedicated to process step (ii), the intermediate storage of bins, which is in the focus of this paper. Once a batch is completed and all bins have arrived in the ASRS, the bin sequence in which they are released into the consolidation area has to be determined. To the best of our knowledge in business practice, bins are mostly released in random sequence. In this paper, we aim at optimized release sequences. Specifically, we aim to minimize the sum of order completion times. An order is completed once all belonging items have been sorted into the respective shelf of the put wall. This way, we aim to quickly sort orders into the put wall, so that the probability of starving packers waiting idle for completed orders is minimized. This problem has not been treated in the literature yet. The only other paper dealing with release sequences of bins into the consolidation area is provided by Boysen et al. (2016). They, however, treat a setting where an automated conveyor-based sorting system is applied instead of a put wall. To reduce the probability of deadlocks where no lane for collecting items is available, they aim to minimize the order spread within the release sequence. Thus, a completely different consolidation technology and another objective function is applied compared to the paper on hand.

Existing research on order consolidation [process step (iii)] exclusively treats automated conveyor-based sorting systems (see Meller 1997; Johnson 1998; Petersen 2000; Johnson and Meller 2002; Russell and Meller 2003; Briskorn et al. 2017). Manual order consolidation, however, has (to the best of the authors’ knowledge) not been treated in the literature yet. We simulate the consolidation and packing process if a put wall is applied for manual order consolidation. In this way, the impact of different bin release sequences from the ASRS can be evaluated with regard to their impact on consolidation performance.

Sequencing of item retrievals from an ASRS is a vividly researched topic. Survey papers are provided by Roodbergen and Vis (2009) as well as Boysen and Stephan (2016). This stream of literature, however, focuses reducing the effort for the storage and retrieval machine that moves the items between their storage positions and the input–output point. Our sequencing approach presupposes that the ASRS is not the bottleneck. Instead, we aim at an efficient manual consolidation process and optimize the release sequence of bins according to this aim. From a methodological point of view, our problem is closely related to single machine scheduling. The jobs processed by a machine equal the bins to be released from the ASRS. Our objective is to minimize the completion times of orders, such that the packers’ idle times are reduced. The single machine scheduling problem minimizing the sum of completion times is well known to be solvable in polynomial time (Smith 1956), whereas our problem where each job (bin) may contribute to completing multiple orders is shown to be strongly NP-hard. The main difference between machine scheduling and our problem is that the former either has a 1:1 relation between each job and the order the respective job refers to or a 1 : n relation where multiple jobs, e.g., in a job-shop, open-shop or flow-shop environment, are to be processed to complete an order. In our problem, we have a m : n relation instead. Each job (bin) contains items for many orders and each order requires items from multiple bins. An additional major distinction to open-shop and flow-shop scheduling problems is that we have just a single machine (i.e., the ASRS). Thus, we treat a very basic, yet (to the best of the authors’ knowledge) novel extension of traditional machine scheduling.

It can be concluded that this paper treats a novel optimization problem, which has not been treated in the scientific literature yet.

1.3 Contribution and paper structure

This paper aims to optimize the bin sequence in which a batch of orders is released from intermediate storage into the consolidation area.The batch of orders is assumed to be already completely assembled in the ASRS after being picked under a batching and/or zoning policy. We aim at a release sequence of all bins from the ASRS, such that orders are quickly sorted into the put wall and unproductive idle time of packers is avoided. Our optimization objective for the bin sequencing problem is to minimize the sum of completion times at which orders are readily assembled in the put wall. The impact of optimized bin sequences on the subsequent packing process on the other side of the wall is evaluated by a simulation study. This way, we quantify potential performance gains of optimized release sequences (compared to random sequences) in different warehouse settings. The contribution of this paper is, therefore, twofold. From a methodological point of view, we treat a basic extension of single machine scheduling where we have a m : n relation among the job processed and the orders these jobs belong to. We settle computational complexity for the sum of completion times objective and provide exact and heuristic solution procedures. From an application perspective, we show that an optimized release of bins from intermediate storage has the potential to considerably improve consolidation performance compared to the random release sequences that are typically applied in real-world warehouses.

The remainder of the paper is structured as follows. Section. 2 defines our batched order bin sequencing problem and investigates computational complexity. Suited exact and heuristic solution procedures are developed in Sect. 3, whose computational performance is investigated in Sect. 4. Then, Sect. 5 introduces the setup of our simulation study and explores the impact of optimized release sequences on the packers’ idle time. Finally, Sect. 6 concludes the paper.

2 The batched order bin sequencing problem

2.1 Problem definition

This section defines the batched order bin sequencing (BOBS) problem, which decides on the release sequence of bins from intermediate storage into the consolidation area. Our batch of orders \(O=\{1,\ldots ,m\}\) has been picked under a batching and/or zoning policy, so that the items of this batch are spread over a set \(I=\{1,\ldots ,n\}\) of bins. Depending on the specific content of the bins sets \(I_o\subseteq I\) define the subset of bins, which contain at least one item for order o. Processing a bin at the put wall requires the putter to withdraw item after item from the bin. The putter scans the current item, so that the put-to-light mechanism can indicate the shelf where the respective order is collected, and puts the item into the shelf. Depending on the number of items contained in a bin, processing bin i takes processing time \(p_i\). A specific bin sequence is represented by a sequence \(\phi\), i.e., a permutation of bins \(i=1,\ldots ,n\), with \(\phi (k)\) returning the bin at sequence position \(k=1,\ldots ,n\). Let \(\kappa (\phi ,o)=\max \{k=1,\ldots ,n: \phi (k) \in I_o\}\) be the sequence position of the last bin containing items for order o. Among all sequences \(\phi\), BOBS seeks one which minimizes

$$\begin{aligned} Z(\phi )=\sum _{o \in O} \sum _{k=1}^{\kappa (\phi ,o)} p_{\phi (k)}. \end{aligned}$$

Thus, we aim to optimize the sum of completion times at which all items of each order are readily placed in the respective shelf of the put wall. This way, the orders of the batch are quickly assembled, so that unproductive idle time of packers on the other side of the wall is reduced.

BOBS is based on some (simplifying) assumptions, which we elaborate in the following:

  • The bins are intermediately stored in an ASRS until all bins of the batch have arrived. With regard to the retrieval process we assume that the ASRS is able to release the bins in arbitrary sequence. Thus, assignment restrictions where specific sequence positions are forbidden for some bins are a non-issue.

  • All data is assumed to be deterministic. Thus, there are no inventory differences of items missing or being picked into wrong bins. We also assume that the number of items per bin is a reliable predictor for the processing time, so that modelling it as deterministic is not too far away from real-world operations.

  • Typically, no information on the stacking plan of items within a bin is available. Thus, the retrieval sequence of items from a bin is unknown. Therefore, we take some worst-case perspective and assume that an order is completely stored in the wall not before the complete processing time of its final bin has elapsed.

  • To simplify the optimization problem we do not explicitly model the packing process behind the wall. The total completion time is just a surrogate objective for an efficient packing process. It will be part of our simulation study in Sect. 5 to explore whether our proxy is indeed well suited to improve packing productivity.

Fig. 2
figure 2

Two alternative bin sequences for the example

Full size image

Example 1

Consider the example of Fig. 2 where a batch of \(m=4\) orders is spread over \(n=5\) bins. Items are represented by circles within the bins and the orders these items are dedicated to are referenced by the numbers within the circles. The processing times of the bins correspond to the number of items contained, so that a bin i with two items inside is supposed to have a processing time of \(p_i=2\). Figure 2 depicts two alternative solutions. Solution (a) has a total completion time of \(Z(\phi )=39\), whereas solution (b) only amounts to \(Z(\phi )=34\).

2.2 A mixed-integer program

Based on the notation presented in Table 1, BOBS can be formulated as a mixed-integer programming (MIP) model, which consists of objective function (1) and constraints (2) to (7).

$$\begin{aligned} {\mathbf{BOBS-MIP}}{\colon}\quad {\text {Minimize}} Z(C,X,Y) = \sum _{o \in O} y_o \end{aligned}$$
(1)

subject to

$$\begin{aligned} \sum _{i \in I \cup \{0\}} x_{i,j}= & {} 1 \quad \forall j \in I \cup \{n+1\}\end{aligned}$$
(2)
$$\begin{aligned} \sum _{j \in I \cup \{n+1\}} x_{i,j}= & {} 1 \quad \forall i \in I \cup \{0\}\end{aligned}$$
(3)
$$\begin{aligned} C_i - (1 - x_{i,j}) \cdot M\le & {} C_j - p_j \quad \forall i \in I \cup \{0\}, j \in I \cup \{n+1\}\end{aligned}$$
(4)
$$\begin{aligned} C_0= & {}\, 0\end{aligned}$$
(5)
$$\begin{aligned} C_i\le & {} y_o \quad \forall o \in O, i \in I_o\end{aligned}$$
(6)
$$\begin{aligned} x_{i,j}\in & {} \{0, 1\} \quad \forall i \in I \cup \{0\}, j \in I \cup \{n+1\} \end{aligned}$$
(7)

Objective function (1) minimizes the sum of completion times of all orders. Constraints (2) and (3) make sure that the sequence of bins is well defined. Constraints (4) set the completion times of bins and avoids overlap of their processing intervals. The first (virtual) bin with index 0 has completion time 0 (see constraint 5) and the orders’ completion times are set by (6). Finally, constraints (7) define the domain of the binary variables.

Table 1 Notation
Full size table

2.3 Computational complexity

In this section, we investigate the complexity status of BOBS and prove NP-hardness in the strong sense. The transformation is from the linear arrangement problem (LAP), which is well-known to be NP-complete in the strong sense (see Garey and Johnson 1979).

LAP: Given a graph \(G=(V,E)\) and a positive integer K. Is there a one-to-one-function \(\vartheta :V\rightarrow \{1,2,\ldots ,|V|\}\), i.e., a numbering of nodes V with integer values from 1 to |V|, such that \(\sum _{(u,v) \in E} |\vartheta (u)-\vartheta (v)| \le K\)?

Theorem 1

BOBS is strongly NP-hard even if all bins have unit processing time, i.e., \(p_i=1\) for all \(i=1,\ldots ,n\).

Proof

Within our transformation of LAP to BOBS we introduce a bin for each node, so that \(n=|V|\). The integer value \(\vartheta (u)\) assigned to a node u within LAP corresponds to the sequence position \(\phi ^{-1}(i)\) assigned to bin i within BOBS. Given the maximum degree \(\delta (G)=\max _{u\in V}\left\{ \left| \left\{ v\in V:(u,v)\in E \right\} \right| \right\}\) of the LAP graph, we introduce \(\delta (G)\) orders for each node \(u \in V\): First, an order \(\{u,v\}\) is generated for each adjacent node v, so that for each edge \((u,v) \in E\) two orders \(\{u,v\}\) and \(\{v,u\}\) are generated. Then, for each node having a degree less than \(\delta (G)\) we extend the order set by additional single-bin-orders \(\{u\}\) until \(\delta (G)\) orders per node are generated. In total, \(\delta (G)\cdot |V|\) single- and two-bin-orders are introduced. The question we ask is whether we can find a solution for BOBS with objective value

$$\begin{aligned} Z=\delta (G)\cdot \frac{|V|\cdot (|V|+1)}{2}+K. \end{aligned}$$

Obviously, this transformation can be done in polynomial time. The \(\delta (G)\) orders associated with each bin u are either single-bin-orders, which have completion time \(\phi ^{-1}(u)\), or two-bin-orders. Each order \(\{u,v\}\) of the latter kind always exists twice, because in the name of each edge (u, v) two identical orders are introduced, i.e., one when generating the \(\delta (G)\) orders for node u and the other when generating orders for v. The unit processing times allow us to measure completion time in sequence positions of the bin sequence. The sum of completion times for both of these orders is, thus, twice the sequence position of the later of both bins u and v. If \(\phi ^{-1}(u)<\phi ^{-1}(v)\), this amounts to \(2\phi ^{-1}(v)\). Due to the inequality of \(\phi ^{-1}(u)\) and \(\phi ^{-1}(v)\), we can rearrange \(2\phi ^{-1}(v)\) to \(\phi ^{-1}(v) + \phi ^{-1}(u) + (\phi ^{-1}(v) - \phi ^{-1}(u))\). If we assign the former two time spans \(\phi ^{-1}(v)\) and \(\phi ^{-1}(u)\) to bins v and u, respectively, then it becomes obvious that to each sequence position \(i=1,\ldots ,n\) exactly \(\delta (G)\) time spans are assigned. Thus, we have an inevitable amount of completion time, i.e., independent of the sequence positions of bins, of

$$\begin{aligned} \delta (G)\cdot \sum _{u\in V}\phi ^{-1}(u)=\delta (G)\cdot \sum _{i=1}^{|V|}i=\delta (G)\cdot \frac{|V|\cdot (|V|+1)}{2}. \end{aligned}$$

The remaining time spans \(\phi ^{-1}(v)-\phi ^{-1}(u)\) within BOBS, which are dependent of the sequence positions of bins, exactly equal the difference in the node numbers assigned to each edge within LAP, so that both problems are directly transferable from each other and the theorem holds. \(\square\)

Fig. 3
figure 3

Example for the transformation of LAP to BOBS

Full size image

Example 2

For a more intuitive understanding consider the LAP instance given in Fig. 3a and its belonging optimal linear ordering (b) with an objective value of \(K = 6\). The orders to be generated are illustrated in the put wall on the left side of Fig. 3c. The corresponding BOBS bin sequence with

$$\begin{aligned} Z=3\cdot \frac{|V|\cdot (|V|+1)}{2}+K=\overbrace{\underbrace{2+5+2+3+5}_{ orders\;11\;to\;15}+\underbrace{1+5+3+5+4}_{ orders\;21\;to\;25}+\underbrace{1+5+2+4+4}_{ orders\;31\;to\;35}}^{ completion\;times }=51 \end{aligned}$$

is depicted in (d).

Theorem 1 settles the complexity status for the rather theoretical case of unit processing times. In business practice, however, the processing time varies from bin to bin and depends on the number of items that are contained in each bin. Therefore, the following corollary transfers our previous result to the case where processing times are proportional to the number of items contained in each bin.

Corollary 1

BOBS is strongly NP-hard even if all processing times \(p_i\) equal the number of items contained in bin i for all \(i=1,\ldots ,n\).

Proof

This result immediately follows from the proof of Theorem 1. All we have to do is to make sure that all bins contain the same number c of items. Extending the previous transformation scheme, we fill up each bin, so that each of them contains exactly \(c=2\cdot \delta (G)+1\) items. Additionally, we introduce one extra order requiring all these fill-up items (e.g., at least one item from every bin). This additional order will be completed right after processing the last bin and has, therefore, no further influence on the optimal bin sequence. Although all bins have processing times depending on the number of items contained, the transformation from LAP is still valid, as we seek now for a solution with objective value

$$\begin{aligned} Z= \left( 2\cdot \delta (G)+1\right) \cdot \left( \delta (G)\cdot \frac{|V|\cdot (|V|+1)}{2}+K+|V| \right) . \end{aligned}$$

\(\square\)

3 Solution procedures

This section is dedicated to exact and heuristic solution procedures for BOBS. At first, a simple greedy heuristic is presented in Sect. 3.1. Afterwards, BOBS is tackled by dynamic programming in Sect. 3.2.

3.1 Greedy heuristic

BOBS is an extension of the single machine scheduling problem minimizing the sum of completion times. This problem is well known to be solvable to optimality in polynomial time by applying the shortest-processing-time (SPT) rule (Smith 1956). To transfer the basic logic of the SPT rule to BOBS, where multiple jobs may be required to complete each order, we prioritize all not yet finished (active) orders by their remaining processing time if all missing bins of the respective order are scheduled in direct succession. Among all active orders we select one with the shortest remaining processing time. As a tiebreaker the lower order index is applied. All missing bins of the selected order are, then, added to the sequence. This greedy approach cannot guarantee optimal solutions, but we, nonetheless, hope that our simple adaption of the SPT logic yields solutions with small optimality gaps very quickly. It will be part of our computational study in Sect. 4 to explore whether this hope is justified.

figure a

Algorithm 1 details the greedy procedure in a more formal way using pseudo code. First, the applied data structures are initialized (lines 1–4). Then, we calculate the remaining processing times of all not yet finished (active) orders by adding the processing times of the respective (active) bins not yet processed (lines 6–9). In line 10, we select the active order with the shortest remaining processing time and add all active bins still required by the selected order to the bin sequence (lines 11–14). Then, the selected order is removed from the set of active orders (line 15). We proceed until all orders are processed and, finally, the bin sequence is returned.

Example 1 (cont.): For the example of Fig.2 our greedy heuristic leads to solution (b) and an objective value of \(Z(\phi )=34\).

3.2 A dynamic programming procedure

For determining optimal solutions we introduce a dynamic programming (DP) procedure, which applies the traditional DP scheme for sequencing problems defined by Held and Karp (1962). The decision process of DP is subdivided into \(n+1\) stages, where each stage \(k = 1, \ldots ,n\) represents a sequence position of the bin sequence (plus a virtual start stage 0). We plan the sequence in reverted order and start in final sequence position n. It is the last bin that determines the order’s completion time, so that the reverted order allows gaining at least some completion times quickly. As we extend the basic DP scheme with upper and lower bounds and also apply it in a heuristic beam search procedure, backwards planning showed considerably superior compared to forward planning in preliminary computational tests. Any stage k contains a set of states, where each state represents a possible subset \(I' \subseteq I\), \(|I'|= k\), of bins already assigned to sequence positions \((|I| - k + 1), \ldots , |I|\). The optimum schedule for subset \(I'\) is found according to recursive equations

$$\begin{aligned} h^*(I')= min _{i \in I'} \left\{ h^*(I' {\setminus } \{i\}) + f\left( i, I' {\setminus } \{i\} \right) \right\} \end{aligned}$$
(8)

with \(h^*(\emptyset )=0\). The objective value of the optimal bin sequence for bins \(I' {\setminus } \{i\}\) is added to the contribution \(f(i,I' {\setminus } \{i\})\) of assigning bin i to sequence position \((|I| - k + 1)\) and having bin set \(I' {\setminus } \{i\}\) assigned to subsequent sequence positions \((|I| - k + 2), \ldots , |I|\), where \(f(i,\widetilde{I})\) is calculated according to

$$\begin{aligned} f(i,\widetilde{I})= \left( \sum _{j \in I {\setminus } \widetilde{I}} p_j\right) \cdot |\{o \in O: \, i \in I_o \, \wedge \, I_o \cap \tilde{I} = \emptyset \}|. \end{aligned}$$

The first term in brackets calculates the completion time of the currently assigned bin i by summing up the processing times of the set of not yet fixed bins, which then is multiplied with the number of orders just being completed by bin i. The overall objective of DP is to find optimal solution value \(h^*(I)\) for the set of all bins. We can determine \(h^*(I)\) by a stage-wise recursion using (8). Finally, when stage 0 is reached and optimal solution value \(h^*(I)\) is determined, a simple recursion in reverted direction can be applied to determine the optimal bin sequence.

There are \(2^n\) states and \(n\cdot 2^{n-1}\) transitions to be evaluated. Each transition requires the inspection of all m orders, which in the worst case refer to all n bins. Thus, the computational complexity of DP amounts to \(\mathcal {O}(m \cdot n^2 \cdot 2^n)\), so that (in line with the previous complexity result) there is an exponential increase of runtime in the number of bins n.

To improve the runtime of DP (without altering the worst-case runtime stated above), we additionally consider a global upper bound as well as local lower bounds in each state. The initial upper bound is determined by solving our greedy heuristic (see Sect. 3.1). In each state, we try to improve the upper bound by completing the partial solution represented by the current state and schedule all bins not sequenced yet by applying our greedy heuristic. Note that the set of active orders not yet fixed at the beginning of the iterative greedy procedure is \(\{o \in O: \, I_o \cap \tilde{I} = \emptyset \}\), with \(\tilde{I}\) being the set of bins already scheduled in the partial solution.

The basic idea of our local lower bound procedure is to relax the fact that only one bin can be processed at a time. We assume that each active order is processed as soon as possible, while we only consider pairwise disjunct orders. To determine the local lower bound of a state, we at first determine sets \(\bar{O}_o = \{o' \in O : I_o \cap I_{o'} = \emptyset \}\) of orders being disjunct to order o. Based on these sets of disjunct orders \(\bar{O}_o\) and the set of orders already planned \(\widetilde{O}\), e.g., orders \(o \in O\) with at least one bin \(i \in I_o\) sequenced, we define parameter \(\bar{t}_o\) in each state by

$$\begin{aligned} \bar{t}_o = {\left\{ \begin{array}{ll} \sum _{i \in I_{o}} p_i &\quad \text{if } \bar{O}_o {\setminus } \widetilde{O} = \emptyset \\ \max _{o' \in \bar{O}_o {\setminus } \widetilde{O}}\{\delta _{oo'}\} &\quad \text{otherwise } \end{array}\right. } \quad \forall o \in O {\setminus } \widetilde{O}, \end{aligned}$$
(9)

with

$$\begin{aligned} \delta _{oo'} = {\left\{ \begin{array}{ll} \sum _{i \in I_{o'}} p_i + \sum _{i \in I_{o}} p_i &\quad \text{if } \sum _{i \in I_{o'}} p_i < \sum _{i \in I_{o}} p_i \\ \sum _{i \in I_{o}} p_i &\quad \text{otherwise. } \end{array}\right. } \end{aligned}$$
(10)

This means that for all orders still active \(o \in O {\setminus } \widetilde{O}\) the completion time \(\bar{t}_o\) is assumed to be the earliest possible point in time, which is at least the sum of processing times of the single bins of this order \(\sum _{i \in I_{o}} p_i\) (see Eq. 9). To sharpen the bound, we consider that pairwise disjunct orders cannot be processed in parallel. If two active orders are pairwise disjunct, the one with longer processing times cannot be scheduled before the other one is completed (see Eq. 10). Based on the values \(\bar{t}_o \; \forall o \in O {\setminus } \widetilde{O}\), we can define a local lower bound LB depending on the set of already planned bins \(\tilde{I}\) as

$$\begin{aligned} LB(\tilde{I}) = h^*(\tilde{I}) + \sum _{o \in O {\setminus } \widetilde{O}} \bar{t}_o. \end{aligned}$$

Using these bounds, we can extend our DP scheme to a bounded DP, where states are only further developed if their lower bounds \(LB(\tilde{I})\) are lower than the current upper bound value. If the state space becomes too large our bounded DP scheme can also be heuristically applied in a bounded iterative beam search approach. Using beam search, only the \(\Upsilon\) best states (dubbed beam width) according to their partial costs \(h^*(\widetilde{I})\) are further considered in each stage. The intensity of the beam search, thus, depends on three parameters \((\Omega , \Upsilon _0, \Psi )\). \(\Omega\) represents the number of beam search iterations performed, while \(\Upsilon _0\) is the initial beam width in the first iteration of the DP scheme. To intensify the search with every iteration, the beam width is multiplied with \(\Psi\) in each of the following iterations, such that \(\Upsilon _n = \Upsilon _{n-1} \cdot \Psi = \Upsilon _0 \cdot \Psi ^{n}\) in iteration n. In this way, the upper bound is updated in each iteration, so that a more exhaustive search with a larger beam width is affordable. Finally, after \(\Omega\) iterations the best solution, which equals the current upper bound, is returned.

Fig. 4
figure 4

Bounded dynamic programming graph for Example 1

Full size image

Example 1 (cont.): The resulting DP graph for our example of Fig. 2 is depicted in Fig. 4. Starting with an initial upper bound of 34 provided by the greedy heuristic, the bounded DP approach is able to prove optimality of this solution in stage 3 of the graph. In this stage, the states \(\{1,2,4\}\) and \(\{1,2,5\}\) both represent partial solutions where the completion times of all orders are already known. Therefore, the objective value of the represented set of bin sequences can be computed by \(h^*(\{1,2,4\}) = h^*(\{1,2,5\}) = 1 \cdot 11 + 1 \cdot 10 + 2 \cdot 8 = 37\). As this value is larger than the current upper bound, both states can be fathomed. The already fixed completion times of state \(\{1,2,3\}\) amount to 29, while the completion time of order 2 is not yet known. Since no other order is still active (i.e., \(\bar{O}_2 {\setminus } \widetilde{O} = \emptyset\)), we can determine the local lower bound by \(LB(\{1,2,3\}) = h^*(\{1,2,3\}) + (p_4 + p_5) = 34\). In consequence, this state can be fathomed, too, and optimality of the greedy upper bound solution is proven.

4 Performance of solution procedures

In this section, we investigate the performance of our solution procedures. Since no established testbed is available for our BOBS problem, instance generation is detailed in Sect. 4.1. Then, the performance results of our solution procedures are presented in Sect. 4.2.

All computations have been executed on a 64-bit PC with an Intel Core i7-6700K CPU (4 \(\times\) 4.0 GHz), 64 GB main memory, and Windows 7 Enterprise. The procedures have been implemented using C# (Visual Studio 2015) and off-the-shelf solver Gurobi (version 7.0.2) has been applied for solving the MIP model.

4.1 Instance generation

We generate two differently sized datasets for our computational study. The instances in the small dataset are still solvable to optimality using our bounded DP approach, while the large instances are of real-world size, so that only heuristic solutions can be obtained by our procedures. The parameters handed over to our instance generator are listed in Table 2. The parameter values are chosen based on personal information from practitioners. We generate 25 instances per parameter setting, so that we receive 75 small and 75 large instances. In the following, we detail how each single instance is obtained.

Table 2 Parameter values for instance generation
Full size table

In a first step, we draw the quantity of bins per order from a standard normal distribution having mean value \(\mu\) and standard deviation \(\sigma\). Note that, for obvious reason, each order is at least contained in one bin, so that we cut the lower end of the standard normal distribution. We also check if the total number of bins is less than or equal to the sum of bins over all orders. If not, we return to the first step, otherwise we assign one randomly chosen order to each bin to ensure that each bin contains at least one order. Then, we draw the remaining bins of each order with equal probabilities. Having a mapping between bins and orders, we set the number of items of each order in a bin by drawing an integer from interval [1; 3] using a uniform distribution. Based on the assumption that the scanning and putting process for each item lasts 4 s, the processing time of each bin is finally computed.

4.2 Computational performance

In this section, we compare the solution quality of our two exact procedures, i.e., Gurobi solving the MIP model presented in Sect. 2.2 and our bounded DP of Section 3.2. Furthermore, we benchmark the two heuristic approaches, i.e., our greedy heuristic of Sect. 3.1 and the iterative beam search (IBS) procedure of Sect. 3.2. Table 3 summarizes the results for the small dataset. For all four solution methods, we report the average relative gap to the optimal solution (gap), the number of optimal solutions obtained (#opt) by the respective approach, and the average CPU seconds (s). IBS is executed with steering parameter values \((\Omega , \Upsilon _0, \Psi )=(10,1.5,8)\), which in preliminary computational tests showed a promising performance. The following conclusions can be drawn from these results:

  • When comparing the exact solution procedures, it can be concluded that bounded DP clearly outperforms standard solver Gurobi. Although Gurobi uses all its allowed solution time (i.e., the timeout is set to 600 s) it only solves 15 out of 75 instances (20%) to optimality. For none of these instances the optimum is proven. On average, the gap to the optimal solutions is more than 1.2%. Bounded DP, instead, is able to find all optimal solutions in only 5 s on average.

  • Our heuristic methods also lead to promising results. IBS also finds all optimal solutions, while the average time consumption of this approach is only half a second. The greedy heuristic is even faster. Its time consumption is barely measurable and the average gap is only 1.0%, which is even better than the optimality gap produced by Gurobi.

Table 3 Computational results for the small dataset [gap to optimal solution (gap)/number of optimal solutions found (#opt)/computation time in seconds (s)]
Full size table
Table 4 Computational results for the large dataset [gap to best solution (gap)/number of best solutions found (#best)/computation time in seconds (s)]
Full size table

When solving the large dataset both bounded DP and Gurobi ran out of memory, so that optimal solutions are not available. We, thus, only benchmark our two heuristic approaches and report the gap to the best solution found by both competitors (gap), the number of best solutions (#best), and the average computational time (s). IBS is executed with steering parameter values \((\Omega , \Upsilon _0, \Psi )=(25,2.0,15)\). As can be seen in Table 4, the time consumption of the greedy approach is still barely measurable and its average gap to the best solutions found by IBS after more than an hour of computational time is less than 1.5% on average. Given the long runtime of IBS and a selection of steering parameters, which increases the number of iterations and states generated per stage compared to the small dataset, we conjecture that IBS comes pretty close to the optimal solutions. If this is true, our simple greedy heuristic leads to an astonishingly good performance and solves even large-sized instances with very good results. Therefore, we apply the greedy heuristic for all following tests, where we explore the impact of optimized bin release sequences on the performance of the consolidation process.

5 Managerial aspects

In this section, we address some managerial aspects. To explore the impact of different bin release sequences we apply a simulation study, where work of the putter and the packer in the consolidation is emulated. The setup of the simulation is described in Sect. 5.1. With the help of the simulation we can explore whether our surrogate objective for deriving the bin release sequence is indeed a good choice. In Sect. 5.2, we compare the performance of optimized and random bin release sequences. In Sect. 5.3, we investigate how our performance measures are influenced by important system characteristics, i.e., packing speed, the number of packers, and differently sized batches. In this way, we gain insight into optimal process design and identify scenarios in which optimization considerably speeds up order consolidation and others where not.

Note that considering a deterministic offline scheduling problem is no shortcoming from the practitioner’s point of view. We presuppose that the complete batch of orders is first assembled in intermediate storage, only once all bins belonging to the same batch have arrived they are released into the consolidation area. This is exactly the mode of operation we observed in business practice. The next batch of orders to be picked is selected among all those orders whose cutoff date is approaching. According to the zones the requested items of these orders are stored in, the set of bins to be picked next is derived. Identified by the barcodes on the bins the system controls the arrival of all bins belonging to a batch and marks it as completed finally. Completed batches, which are pairwise disjunct, are successively released towards the put wall. In this way, an excessive blocking of sortation capacity due to some required but not yet picked items is avoided (see Sect. 1.1). Our approach is, thus, easily implementable in real-world operations. A completed batch of bins has to be retrieved in a specific sequence that is to be announced to the IT system of the ASRS anyway. Instead of announcing just some random bin sequence, which is the current approach at least in the warehouses we visited, it is easily possible to hand over an optimized bin sequence without any further investment into hardware.

5.1 Setup of simulation study

In the simulation study, we emulate the consolidation process of a single putter and one or multiple packers in the consolidation area. Each simulation run covers 21 batches of orders spread over multiple bins, which successively arrive in the consolidation area to be processed. The first batch is used as a tuning phase, whereas the remaining ones are used to collect performance data.

Each batch is equivalent to a problem instance of our BOBS problem. Consequently, we generate each batch in the same way as we generate our large problem instances using a \(\sigma\) value of 1.5 (see Sect. 4.1). Furthermore, we have to define some additional simulation parameters, which are summarized in Table 5. Note that the bold parameter values are the default values, which are applied if not explicitly stated otherwise. Once again, we chose these values based on personal information of practitioners or averaged data collected during warehouse tours. We generate 100 basic simulation instances, which are adapted to the different parameter values of Table 5, such that each data point in the figures of Sect. 5.3 represent the average result of 100 simulation runs.

Table 5 Parameter values for simulation study
Full size table

The basic setup of our simulation study is based on a put wall configuration, which we observed at an Amazon facility and is schematically depicted in Fig. 1. On one side of the put wall, the putter receives the bins via a conveyor belt. He/she successively removes items from the bins, scans them, and puts them into the rack. In business practice, these steps consume about 4 s of working time per item. On the other side of the put wall one or multiple packers withdraw completed orders, pack them into cardboard boxes, and hand them over to a conveyor system. Depending on the size and weight of products and the technical support equipment time consumption of the packing process can vary within a broad range. As a default value we assume 20 s for packing each completed order, but we vary this value to explore the impact of differing packing speeds.

Putting and packing on both sides of the wall impacts each other. Once a predefined fill level of the put wall is reached, the background IT system initiates the release of the next batch of orders from intermediate storage, so that the respective bins timely reach the put wall once the previous batch is completed and the put wall is empty again. Only then, the putter starts filling the shelves of the put wall with the next batch of orders. Thus, the putter is idle once the last bin of the previous batch is placed in the wall until the next batch starts again, so that the length of the idle time depends on how fast the packers complete the orders. On the other side of the wall, packers may have to wait for the putter if right after completing their previous order the next order is not yet available. These interdependent waiting times on both sides of the wall are recorded by our simulation, which leads us to the three performance indicators of our simulation:

  • average putter idle time,

  • average packer idle time, and

  • average makespan of a batch.

With these performance indicators on hand, we can test whether optimized bin release sequences can indeed speed up the consolidation process.

5.2 Appropriateness of surrogate objective

Minimizing the sum of completion times within BOBS is just a surrogate objective for the efficiency of the consolidation process. Therefore, we have to test whether optimized bin release sequences positively impact our three performance indicators. To evaluate this, we derive an optimized BOBS sequence with our greedy heuristic and a random bin sequence for each instance. Recall that in business practice, typically, random release sequences are applied. Each simulation instance is run twice, once based on an optimized bin release sequence and once more for a random sequence. For both settings, the performance measures of the consolidation process derived by the simulation are recorded and compared. The results of this test averaged over our 100 basic simulation instances are summarized in Table 6. Here, we report all three performance measures as well as the relative (percentage point) reduction of the respective performance indicator of optimized bin sequences in relation to random ones and the p-value of a paired two-sample t-test. Note that the relative (percentage point) reduction is calculated by \((Z^\mathrm{sim}(rnd)-Z^\mathrm{sim}(\phi ))/Z^\mathrm{sim}(rnd)\), where \(Z^\mathrm{sim}(rnd)\) and \(Z^{sim}(\phi )\) denote the value of the respective performance measure obtained by simulation for the random and the optimized bin sequence, respectively.

Table 6 Results of simulation study for optimized and random bin sequences
Full size table

These results clearly indicate that both resources, i.e., the putter and the packer, are more efficiently utilized if optimized bins release sequences are applied. The idle time of the putter (packer) is significantly reduced by 68.77% (73.8%). Additionally, our optimization approach reduces the average makespan of a batch by more than a minute, which results in a reduction of 14.38%. Note that the p-values of the paired two-sample t-tests indicate that the advantages of optimized over randomized bin sequences are statistically significant. Further note that the (theoretical) lower bound of the average makespan per batch, determined by the sum of processing times of all bins plus the packing time of the last order, amounts to 416.2 s. Our optimized bin release sequences have a gap to this bound of only 1.4%, while the randomized simulation runs have a gap of 18.5%. Thus, our optimized bin sequences lead to a consolidation performance, which is pretty close to the optimum.

It can be concluded that optimized bin release sequences considerably speed up the consolidation process and our surrogate objective applied within BOBS seems well suited. This conclusion holds for our default setting of simulation parameters. In the following section, we explore the impact of different parameters, i.e., packing time, the number of packers, and the number of bins over which each batch is spread, on consolidation performance.

5.3 On the impact of varying system parameters

The packing time it takes a packer to pack an order into a cardboard box considerably varies in business practice. It depends, for instance, on the size and weight of the handled products, the type of packaging, and whether additional protective packing material, advertising flyers, and invoices have to be added. Furthermore, technical equipment to automatically erect, close, seal, and label cardboard boxes can be applied to further reduce manual operations. To gain insight into the effect of different packing times we run our simulation for optimized and random bin release sequences for varying parameter values of the packing time (see Sect. 5.1).

Fig. 5
figure 5

Performance benchmark for varying packing speed

Full size image

The results depicted in Fig. 5 show that optimized bin release sequences considerably improve consolidation performance only in a corridor where the packing times range somewhere between 15 and 30 s. In this corridor, which (at least to our experience) contains most packing times relevant in online retailing, the ratio between putting and packing times is rather balanced. A quick assembly of orders in the put wall (as is enabled by our BOBS objective) leads to a better synchronization of putting and packing and, thus, to considerable performance gains. If the system is rather unbalanced, however, no improvement over random sequences can be realized. If the packing time is very short, e.g., only 8 s because all process steps except for the retrieval of items from the wall and their placement in an already erected cardboard box are automated, then the putter is the unique bottleneck of the consolidation process and the packer is idle for more than half of the makespan. On the other hand, if the packing time is large, e.g., 60 s because large, heavy, and/or fragile items need to packed in a completely manual process, the packer is the unique bottleneck and the putter is idle for more than half of the makespan. In both cases, the system is in imbalance which cannot be countervailed by merely optimizing bin release sequences. One lever to balance the system whenever one side is considerably faster than the other is to increase the division of labor on the other side. The impact of multiple packers is considered in the following paragraph.

Fig. 6
figure 6

Performance benchmark for a differing number of packers

Full size image

The performance results when varying the workforce of packers are depicted in Fig. 6. More packers have a similar effect like shortening packing times. The makepan is reduced, until the putter becomes the unique bottleneck and no further improvement can be realized. In our default setting, even having just two packers seems not advisable. The processing time of a batch is shortened by about 5% and the putter is fully utilized, but the second packer is idle most of the time. The mean value of the relative idle time per packer is 49.9%, such that this setting can only be recommended if the average makespan per batch is to be reduced for any price.

Finally, we investigate the following question: given a batch of orders to be collected, is it better to collect the items in fewer bins or is it advantageous to distribute the items among more bins? With regard to the picking process more bins means more pickers that collect items concurrently. A larger division of labor accelerates the parallel assembly of the batch, which is an important effect in times of tight delivery times. On the other hand, more pickers increase wage costs and reduce the number of items to be collected per picker and tour. The latter increases the frequency of returns to the depots, so that additional (unproductive) walking results. With regard to order picking these effects are well researched in the literature (see Sect. 1.2). We investigate the impact of the bin number on the consolidation process. For this purpose, we spread the batches of our simulation dataset over varying quantities of bins, while all other instance parameters introduced in Table 2 receive their default value.

Fig. 7
figure 7

Performance benchmark for a differing number of bins

Full size image

Figure 7 summarizes the results if batches are distributed over varying numbers of bins. With just a few bins, no considerable improvement can be achieved by optimized bin sequences. In the very extreme, if all orders are collected in a single bin, we, naturally, have no difference between random and optimized sequences. Already with 10 bins, however, over which our 20 orders are spread all three performance measures considerably profit when employing optimized instead of random sequences. The more bins we have, the shorter the processing time of each single bin, which leads to less waiting times for putter and packer on both sides of the wall. Thus, random sequences profit from more bins too. This effect, however, is much more pronounced if optimized bin release sequences are applied. The more bins we have, the more flexibility there is to reduce the completion times of orders, which, in turn, increases consolidation performance. Thus, more bins induce more unproductive walking effort during order picking, but lead to a more efficient consolidation process, and vice versa. Both effects need to be carefully traded off against each other when setting up warehouse operations.

In summary, our computational tests suggest that optimizing the release sequence of bins from intermediate storage is unhelpful for unbalanced systems, where the packing time is very short or extraordinarily long or too many packers are applied, so that a unique bottleneck on either side of the wall exists. Too few bins and, thus, few sequencing flexibility has the same effect. In these cases, optimization cannot improve over random bin sequences. However, if the working speed on both sides of the wall is rather balanced, then bin release sequences optimized according to our BOBS approach considerably outperform random sequences. Well-balanced systems have no unique bottleneck, which in our simulation is avoided for a single packer having packing times between 15 and 30 s. Furthermore, optimization leads to considerable advantages if the number of bins a batch is contained in is large.

6 Conclusion

This paper considers manual order consolidation based on put walls. Batches of orders are picked according to a batching and/or zoning policy and arrive in an intermediate storage system. We show that optimized sequences in which these bins are finally released from intermediate storage into the consolidation area can considerably reduce the putter’s and packer’s idle times on both sides of the put wall. This is good news for practitioners, because a better consolidation performance can be achieved without any further organizational adjustments; only the desired bin sequence has to be computed and communicated to the storage and retrieval machine operating the intermediate storage system. Specifically, our bin sequencing problem aims to minimize the sum of order completion times. We show that this optimization problem is strongly NP-hard and provide suited exact and heuristic solution procedures. In our computational tests, we show that a simple priority rule based approach leads to an astonishingly good solution performance. Furthermore, we quantify the performance gains of optimized versus random bin release sequences for different warehouse settings.

Put walls need not be fixedly erected on the shop floor, but they also exist equipped with small wheels in form of mobile put walls. With mobile walls, the manual consolidation process is organized slightly different. The putter fills a wall with a batch of orders and rolls it towards the packing workstations of packers. In this setting, idle time of packers can be avoided if the putter timely delivers the new wall towards each station before the current wall is completely depleted. On the other hand, the delivery process increases the unproductive time of the putter. With mobile put walls, optimizing the bin release sequence is not worthwhile, because the makespan of completely filling each wall, such that it can be delivered, is not impacted by the bin release sequence. All bins have to be processed anyway and the sequence does not matter. However, future research should compare consolidation processes based on mobile and immobile put walls, e.g., by a simulation study, such that practitioners having to decide between both alternatives receive some decision support. From a theoretical point of view, our optimization problem is closely related to traditional machine scheduling where, however, we have a m : n relation between jobs (bins) and orders (see Sect. 1.2). Given this fundamental extension of machine scheduling, not only the sum of completion times is an interesting optimization objective, but also all other traditional objectives, e.g., lateness-related objectives, seem worth being investigated. Complexity results as well as exact and heuristic solution procedures are required here.