Dual-Command Operation Generation in Bi-Directional Flow-Rack Automated Storage and Retrieval Systems with Random Storage Policy

Abstract

In the bi-directional flow-rack (BFR) automated storage and retrieval systems (AS/RS), bins slope to opposite directions to make unit-loads be retrieved from half bins and be stored to the other half on the same working face. For random storage policy, a batching-greedy heuristic (BGH) has been proposed to generate dual-command (DC) operations in BFR AS/RS. In this paper, a novel DC operation generation rule specially designed for the BFR AS/RS is introduced to BGH, of which the effectiveness and efficiency are evaluated by simulation experiments.

13.1 Introduction

Automated storage and retrieval systems (AS/RSs) have been widely arranged in unit-load warehouses [1, 2] to obtain high storage accuracy, high throughput capacity and reasonable labor cost. For improving the floor space utilization, double-deep AS/RS [3], flow-rack AS/RS [4], 3D compact AS/RS [5], mobile rack AS/RS [6] and puzzle-based AS/RS [7] have been designed since 2005.

The bi-directional flow-rack (BFR) AS/RS was modified from the flow-rack AS/RS [8]. In a BFR, bins slope to opposite directions to ensure that unit-loads can be retrieved from and stored to both working faces. Therefore, dual-command (DC) operation, which stores a unit-load and retrieves another one within a single cycle to reduce the travel time of handling machine [9], can be generated in BFR AS/RSs. A batching-greedy heuristic (BGH) has been proposed for DC operation generation in BFR AS/RS with random storage policy [8]. However, the generation rule, NN (Nearest Neighbor) [10], SL (Shortest Leg) [10], and SDC (Shortest DC time) [11], applied by BGH for DC operations are designed for single-deep AS/RSs. Therefore, a novel rule considered the structure of BFR AS/RS is introduced to BGH and its effectiveness and efficiency are evaluated by simulation experiments in this paper.

The rest part is as follows. In Sect. 13.2, BGH and a novel selection rule are introduced. The effectiveness and efficiency of the selection rule are evaluated in Sect. 13.3, followed by some conclusions in Sect. 13.4.

13.2 BGH and the Novel Generation Rule

An $L \times H \times M$ BFR is illustrate in Fig. 13.1. The BFR contains L columns (L is even) and H rows of bins. Each bin consists of M segments to store at most M unit-load. Bins slope from $F_B$ to $F_A$ in Column $1, 3, \ldots , L - 1$ and from $F_A$ to $F_B$ in Column $2, 4, \ldots , L$. Correspondingly, unit-loads slide from $F_B$ to $F_A$ in odd columns and from $F_A$ to $F_B$ in even columns driven by gravity. In each bin, unit-loads follow FIFO (first-in-first-out) rule, which implies that outgoing unit-loads are blocked by blocking unit-loads with certain probability. Blocking unit-loads must be removed before retrieving requested unit-loads. Removed blocking unit-loads are stored to bins on the same working face.

Fig. 13.1

An $L \times H \times M$ BFR

Two handling machines are arranged to $F_A$ and $F_B$, respectively. $t_h$ is the travel time between two horizontal adjacent bins and $t_v$ is the travel time between two vertical adjacent bins. Let $(x_i, y_i)$ represent bin i locates at Column $x_i$ and Row $y_i$ and $(x_j, y_j)$ represent bin j locates at Column $x_j$ and Row $y_j$. Let $c_i = \max \{t_h x_i, t_v (y_i - 1)\}$ ($c_j = \max \{t_h x_j, t_v (y_j - 1)\}$) be the travel time between i $(j)$ and the P/D station. Similarly, $c_{ij} = \max \{|x_i - x_j|t_h, |y_i - y_j|t_v\}$ is the travel time from i $(j)$ to j (i). The normalization and the shape factors of an $L \times H \times M$ BFR are $T = \max \{t_hL, t_vH\}$ and $b = \min \{\frac{t_hL}{T}, \frac{t_vH}{T}\}$, respectively.

In the random storage policy, any stored unit-load can be requested and an incoming unit-load can be stored to any available bin (a bin contains at least one idle segment). The sequencing of unit-loads is denoted as $S = (s_1, s_2, \ldots , s_N)$, in which incoming unit-loads must be handled one by one. As well, the set of outgoing unit-loads is represented as $R = \{r_1, r_2, \ldots , r_N\}$, in which outgoing unit-loads can be retrieved by any order.

The position of an idle segment is an opening and the position of an outgoing unit-load is a retrieval. I is the set of openings. $J = \{j_1, j_2, \ldots , j_N\}$ is the set of retrievals, in which $r_k$ locates at $j_k$ where $k \in \{1, \ldots , N\}$. Let $I_j$ be the set of openings located on the same working face of j. $C_j$ is the travel time of removing and re-storing blocking unit-loads for retrieval j.

In a BFR AS/RS, a unit-load retrieved or removed from $F_A$ ($F_B$) releases an occupied segment on $F_B$ ($F_A$). Therefore, some openings on $F_A$ ($F_B$) become available after retrieving or removing unit-loads from $F_B$ ($F_A$). If such an opening is selected, the process time may be increased because the handling machine may stop to wait for the releasing.

BGH separates incoming unit-loads into batches, for each of which a sequence of DC operations are generated. The released openings in a batch are employed in the following batches to ensure the continuous working of handling machines. Let $P = \lceil \frac{N}{n} \rceil$ be the number of batches. In the pth batch, a total of n or $N - (P - 1)n$ incoming unit-loads and the same number of outgoing unit-loads are conducted by DC operations. BGH is described in Algorithm 1.

In Step 6 of BGH, an opening and a retrieval are selected based on the value of $D_{ij}$. In NN, SL and SDC, $D_{ij} = c_{ij}$, $D_{ij} = c_i + c_{ij}$ and $D_{ij} = c_i + c_{ij} + c_j$, respectively. The time complexity of Step 6 is O(LHN) for NN, SL, and SDC. Let $\rho = \frac{N_u}{LHM}$ be the load rate, in which $N_u$ is the number of stored unit-loads. For a bin, there are a number of K stored unit-loads. Because of the random storage policy, the expected value of K is $E(K) = \rho M$. Therefore, the expected number of blocking unit-loads for a retrieval is $\sum _{k = 0}^{K - 1} \frac{1}{K} = \frac{\rho M - 1}{2}$. The time complexity of choosing openings for blocking unit-loads of a retrieval is $O(LH \frac{\rho M - 1}{2})$. In normal, $\frac{\rho M - 1}{2} < N$, which makes the time complexity of generating a DC operation in BGH with NN, SL, and SDC is O(LHN). Because there are a total of N DC operations to be generated, the time complexity of BGH with NN, SL, and SDC is $O(LHN^2)$.

Because blocking unit-loads are re-stored in DC operations, SDCB (Shortest DC time with Blocking unit-loads) is designed, in which $D_{ij} = c_i + c_{ij} + C_j + c_j$. The time complexity of Step 6 of BGH with SDCB is $O(\frac{\rho M + 1}{2} LHN)$. Correspondingly, the time complexity of BGH with SDCB is $O(\frac{\rho M + 1}{2} LHN^2)$.

13.3 Performance Evaluation

In this section, the effectiveness and efficiency of SDCB are evaluated by simulation experiments. Because SL is better than NN and SDC [8], BGH with SL is executed in simulation experiments for comparing. Simulation experiments are coded in C++. A PC with 2.5 GHz CPU and 16 GB RAM is applied for running simulation experiments.

Let $t_h = 1.0$ and $t_v = 2.0$. In each experiment, a total of 100 instances are conducted. For each instance, let $N = 100$, i.e., 100 DC operations are generated to store 100 incoming unit-loads and retrieve 100 outgoing unit-loads. The batch size takes value of $\{2, 4, 10, 20\}$. The DC operation travel times of instances are recorded, of which the average value is $\mathcal {Z}_{DC}$. As well, the process times of instances are saved, of which the average value is $\mathcal {Z}_{PT}$. In order to narrow the tables, the values of $\frac{\mathcal {Z}_{DC}}{N}$ and $\frac{\mathcal {Z}_{PT}}{N}$ are listed.

Firstly, the impacts of b are analyzed, in which $L \times H \approx 200$, $M = 5$, and $\rho = 0.8$. The values of $\frac{\mathcal {Z}_{DC}}{N}$ and $\frac{\mathcal {Z}_{PT}}{N}$ obtained by BGH with SL and SDCB with different values of b are illustrated in Table 13.1.

Table 13.1 Values of $\frac{\mathcal {Z}_{DC}}{N}$ and $\frac{\mathcal {Z}_{PT}}{N}$ obtained by SL and SDCB with different values of b ($L \times H \approx 200$, $M = 5$ and $\rho = 0.8$)

Table 13.1 indicates that the values of $\frac{\mathcal {Z}_{DC}}{N}$ increase and the values of $\frac{\mathcal {Z}_{PT}}{N}$ decrease with the increase of batch size. The values of $\frac{\mathcal {Z}_{DC}}{N}$ obtained by SDCB become smaller than those gained by SL in large size of batch. The values of $\frac{\mathcal {Z}_{PT}}{N}$ obtained by SDCB are smaller than those gained by SL. SDCB demands much longer CPU time than that spent by SL, which follows the time complexity. With the increase of n, the CPU time required by SDCB decreases.

Then, the impacts of different values of layers are examined and the experimental results are illustrated in Tables 13.2 and 13.3, respectively. In Table 13.2, let $L \times H \times M \approx 1{,}000$, $M \in \{10, 8, 6, 5\}$, $b = 1.0$, and $\rho = 0.8$. In Table 13.3, let $L = 20$, $H = 10$, $\rho = 0.8$, and $M \in \{5, 6, 7, 8\}$.

Table 13.2 Values of $\frac{\mathcal {Z}_{DC}}{N}$ and $\frac{\mathcal {Z}_{PT}}{N}$ obtained by SL and SDCB with different values of M ($L \times H \times M \approx 1{,}000$, $b = 1.0$, and $\rho = 0.8$)

Table 13.3 Values of $\frac{\mathcal {Z}_{DC}}{N}$ and $\frac{\mathcal {Z}_{PT}}{N}$ obtained by SL and SDCB with different values of M ($L = 20$, $H = 10$, and $\rho = 0.8$)

In Table 13.2, the values of n, $\frac{\mathcal {Z}_{DC}}{N}$ and $\frac{\mathcal {Z}_{PT}}{N}$ have the similar changes as those in Table 13.1. SL returns shorter travel time than that gained by SDCB with small batch size and obtains higher travel time than that gained by SDCB with large batch size. SDCB can obtain shorter process time than that gained by SL. As well, SL runs faster than SDCB. The CPU time demanded by SDCB decreases with the increase of n.

Table 13.3 demonstrates that the travel time increases and the process time decreases with the increase of n. SL obtains shorter travel time than that gained by SDCB. SDCB gains shorter process time that obtained by SL. SDCB requires much longer CPU time that demanded by SL. More layers in the BFR implies more blocking unit-loads, which causes the increase of operational cost and the increase of process time.

At last, the impacts of different values of $\rho$ are evaluated by simulation experiments, in which let $L =20$, $H = 10$, $M = 5$, and $\rho \in \{0.75, 0.80, 0.85, 0.90\}$. The experimental results are listed in Table 13.4.

Table 13.4 Values of $\frac{\mathcal {Z}_{DC}}{N}$ and $\frac{\mathcal {Z}_{PT}}{N}$ obtained by SL and SDCB with different values of $\rho$ ($L = 20$, $H = 10$, and $M = 10$)

Table 13.4 shows that the operational cost increases and the process time decreases with the increase of n. SL obtains lower operational cost than that gained by SDCB. SDCB gains shorter process time that obtained by SL. SDCB requires much longer CPU time that demanded by SL. Larger value of $\rho$ implies more blocking unit-loads. Correspondingly, the values of $\frac{\mathcal {Z}_{DC}}{N}$ and $\frac{\mathcal {Z}_{PT}}{N}$ obtained by SL and SDCB increase with the increase of $\rho$.

In summary, the size of batch must be carefully evaluated to balance the operational cost and the process time of DC operations. SL obtains lower travel time and SDCB gains shorter process time. The process time may be more important than the travel time because the process time determines the response time, which is the key parameter of the quality of service (QoS) of a BFR AS/RS.

13.4 Conclusions

In this paper, the SDCB is introduced to the BGH for DC operation generation in BFR AS/RS with random storage policy. Experimental results illustrate that SDCB obtains shorter process time that gained by SL and SL gains shorter total travel time than that obtained by SDCB. The size of batch should be carefully considered to balance the operational cost and the process time. BGH with SDCB is more suitable than BGH with SL in applications where to improve the response time is more important than to reduce the operational cost.

In the future, dual-shuttle machine, which carries two unit-loads simultaneously and has been deployed to flow-rack AS/RSs for improving the retrieval performance [12], can be applied in BFR AS/RSs to enhance the throughput capacity.