Multi-type resources collaborative scheduling in automated warehouse with fuzzy processing time

Abstract

The efficient operation of Intelligent Warehousing System does not rely on individual resource scheduling in stages but multi-type resources collaborative scheduling. In this paper, a collaborative scheduling model for stackers, automated guided vehicles and picking workstations in outbound process is abstracted into a hybrid flow-shop scheduling problem within an automated warehouse scene. Considering the impacts of uncertain factors related to scheduling, the objective function of this model is minimizing the makespan based on the triangular fuzzy processing time. A genetic algorithm is designed to obtain feasible solution of this model with the form of vector coding and the approach of ranking fuzzy numbers. Example analysis shows that the validity of the model and algorithm is verified. Within different resource allocation schemes, their evaluating indexes are significantly different, which are the likely completion time of system operation, the capability coordination degree and the initial investment. Furthermore, the increase of picking workstations is contributed much more to reducing the likely completion time and to improving the capability coordination degree than that of automated guided vehicles.

Keywords

Automated warehouse fuzzy processing time collaborative scheduling genetic algorithm capability coordination degree

1 Introduction

According to the statistics of Gao Gong Industrial Research Institute (GGII), the scale of the intelligent logistic storage system rapidly increased from 2 billion China Yuan (CNY) to 60 billion CNY from 2001 to 2015 as while as the annual average growth rate exceeded 20%. Related market space had exceeded 100 billion CNY in 2018. Automatic storage and retrieval system (AS/RS) is an important facility of the intelligent logistic storage system, and the scale of AS/RS market is expected to reach 32.5 billion CNY by 2020 according to the statistics of China Logistics Technology Association (CLTA) information center. In June 2017, the “Warehouse Robot and Intelligent Industry Alliance” led by the Ministry of Industry and Information Technology (MIIT) was formally established in China. This declared that logistics robots will promote the overall automation level of warehouse.

The automated warehouse is a functional facility consisting of multi-type and multiple resources, such as stackers, automated guided vehicles (AGVs), picking workstations, etc., whose efficient operation depends on the orderly scheduling of the above-mentioned multi-type resources. The aim of the researches of single resource operation mode and scheduling optimization in complex scenes is to eliminate bottlenecks or to make local optimization for sub-systems. However, in complex engineering systems such as AS/RS and KIVA system automated warehouses, the decision preference is to achieve the whole system optimality by the interaction, collaborative operation and joint scheduling of multi-type resources. To this end, the collaborative scheduling problem of multi-type resources in automated warehouses in real-world scenes brings out more research value and practical significance.

For single-type resource scheduling, the present researches focus on large-scale tasks or jobs scheduling in complex systems or multi-mode scenarios scheduling for single-type resource in order to assigning large-scale tasks to those same resources in shortest completion time. Yiheng Kung et al. (2013) [1] proposed an order scheduling method for multiple cranes on a common rail in AS/RS; dynamic programming was used to obtain the best combination of order clustering; and with the method, cooperative work of multiple cranes is achieving and the work efficiency of AS/RS is improving. For such a KIVA system automated warehouse, Yuan Ruiping, Wang Huiling, etc. (2018) [2] established a task scheduling model for multiple AGVs in “goods to picker” order picking mode. They exactly distinguished the synchronous and asynchronous picking scenarios for picking workstations. The shortest makespan to complete all tasks was taken as the planning objective, coevolutionary genetic algorithm based on coarse-grained model was improved to solve the planning models.

For multi-type resources scheduling, the decision-making mainly lies on: (1) selection and combination optimization problems of different scheduling policies from multi-type resources. (2) joint or integrated scheduling of multi-type resources within overall system optimization taking loading, sequencing and allocating as whole. For instance, Sainan Liu (2018) [3] tried to improve the efficiency of the entire automated warehouse system, the integrated scheduling policies of sub-systems of automated warehouse including stacker sub-system, automated guided vehicle(AGV) sub-system and transportation sub-system were discussed and an integrated scheduling model was proposed on the basis of a general automated warehouse layout and the relevance between sub-systems on the operation process; the simulation result showed that it was good for application. Similarly, Jiang Lunshan (2017) [4] researched on joint scheduling of tasks for the stackers and AGVs delivery system of a tobacco raw material AS/RS; a joint scheduling operation time model was established by integrating the process of stackers and AGVs and setting the job priority, and the joint scheduling effect was verified by means of simulation experiments.

Another hot practice in real-world is the handling system of automated container terminal. It can be essentially an automated warehouse system in an open environment. Its resources include quay crane (QC), lifting automated guided vehicle (L-AGV) and automated rail mounted gantry crane (ARMG), etc., whose types are more diverse and complex, and the multi-resource collaborative scheduling optimization problem involved has a more significant impact on improving the overall efficiency of the automated container terminals. Homayouni SM et al. (2013) [5] considered the relationship between quay cranes, automated guided vehicles and handling platforms in SP-AS/RS in the container automated terminal handling system, and established an integrated tasks scheduling model for three types of resources: cranes, vehicles, and the platforms of the SP-AS/RS; a genetic algorithm (GA) was presented to solve this problem accurately and precisely. Tian Yu et al. (2018) [6] and Yang Xue (2019) [7] both attempted to discuss the collaborative scheduling methods of tasks for QCs, L-AGVs and ARMGs under mixed loading and unloading mode in automated terminals, that is, considering the interaction and restriction among various operations of the equipment under the mode, a new mixed integer nonlinear programming model was constructed for QCs, L-AGVs and ARMGs collaborative scheduling, whose objectives were to minimize the ship turnround time at a port and to minimize the operation cost of key equipment, a genetic algorithm based on heuristic strategy was proposed to solve model.

In context, the multi-resource collaborative scheduling issues in automated warehouse can be attributed to a flexible production scheduling problem in scheduling theory, besides above literatures we reviewed in this paper, stronger example is from Didem Cinar et al. (2016) [8] research. They modelled the scheduling problem of truck load operations in AS/RS as a flexible job shop scheduling problem where the loads were considered as jobs, the pallets of a load were regarded as the operations, and the forklifts used to remove the retrieving items to the trucks were seen as machines, a truck loading task scheduling model whose objective was minimization of maximum loading time was established in an AS/RS. Besides, a few scholars such as Guo Jin (2012) [9] defined multiple stackers tasks scheduling in automated warehouses as a parallel machine scheduling problem with features as tasks completed by any one of parallel resources. Whether flexible job shop scheduling or parallel machine scheduling, it depends on the problem defined and its objectives in real-world system. This paper prefers to construct a collaborative scheduling model with system as a whole for automated warehouses based on the hybrid flow-shop scheduling (HFS) method. HFS is kind of combination together with traditional flow shop scheduling and parallel machine scheduling including decisions of one or more machines assignments and jobs sequences in multiple stages.

The minimized maximum completion time, i.e. makespan, is often taken as one of objectives in HFS model. The makespan is directly related to every processing time of jobs in each stage, and they show the obvious feature of uncertainty coming from operation environment, conflicts among joined machines and differences of worker’s skill in real-world scene. The fuzzy processing time is thereby used to describe the uncertainty of makespan in scheduling problems. Jiayu Shen and Yuanguo Zhu (2017) [10], when solving the problem of flexible flow shop scheduling, adopted uncertainty theory to establish a chance constrained framework model considering uncertain processing and repair time subject to breakdowns, and genetic algorithm and particle swarm optimization were used to solve it. In addition, Deming Lei (2010) [11] constructed a flexible job shop scheduling model by quoting fuzzy processing time to assist to measure objective function “minimizing the maximum fuzzy completion time". Jinquan Li et al (2018) [12] and Zhaohong Jia et al (2018) [13] accepted fuzzy processing time to respectively study on a single machine due window assignment scheduling problem and parallel batch processing machines scheduling problem. In those researches, they contributed to find out impacts of uncertain processing time in classical production scheduling but not within real-scene automated warehouses. Fuzzy processing time is also involved in our study because of it is in good way to describe those impacts due to uncertain processing time. In this paper the fuzzy processing time instead of the determined processing time is used to value the objective function of Minimizing the maximum fuzzy completion time of multiple types resources.

To summarize, this paper contributes to the field in the following threes aspects: First, an adapted collaborative scheduling model is proposed in view of an HFS problem which considers the different characters from multi-type and multiple resources within real-scene automated warehouses. Second, the collaborative scheduling with the fuzzy processing time is in consideration to promote the management and control of operating time flexibility for multi-type resources with different operation rules to better meet the realistic requirements in the context of automated warehouses. Last not the least, in our study in order to better optimization in overall system, the capability coordination degree is measured to evaluate the performance of capability coordination among different resources.

Due to the operation characteristics of automated warehouses, collaborative scheduling of multi-type and multiple resources can be defined as an HFS problem with fuzzy processing time. The rest of this paper is organized as following: section 2 redefines and describes the scientific problems; in section 3, the fuzzy processing time of each type resource is defined, and establish a collaborative scheduling model for stackers, AGVs and picking workstations in the outbound process with the minimized maximum fuzzy completion time as the objective function; in sections 4 and 5, a heuristic genetic algorithm is designed for effective solutions with the form of vector coding and the approach of ranking fuzzy numbers; section 6 uses the capability coordination degree as an evaluation index and analyzes the sensitivity of resources allocation to the objective function and the evaluation indexes; the conclusions and prospects are given in section 7.

2 Problem description

The collaborative scheduling problem in the outbound process on an AS/RS automated warehouse from the perspective of system is studied in this paper. Figure 1 shows the layout diagram of a AS/RS automated warehouse, and the automated warehouse in this paper refers to the AS/RS automated warehouse. The three resources of the stackers, AGVs, picking workstations are connected in sequence to complete the outbound process of goods as follows:

When there is a batch of goods that need to be retrieved from the shelves, outbound scheduling instructions are given to the stackers, AGVs and picking workstation to collaborate to finish. First, the stackers take the goods out of the shelves and send them to the outbound buffers of the shelves according to its scheduling instruction.

Then the AGVs receive the delivery instruction including the goods to be shipped and the order of delivery for each AGV, and they move to the outbound buffers of the shelves to take out the goods and send them to the inbound buffers of the picking workstation according to the instructions.

Then the picking workstations receive picking instructions, they sort, pack, and organize the goods according to it. After that, the outbound process is completed.

Fig. 1

The layout diagram of a AS/RS automated warehouse.

The collaborative scheduling problem of AS/RS automated warehouse in the outbound process under the given scene (the location and space are determined) studied in this paper is described as: In the outbound process, in order to improve the overall operation efficiency of the AS/RS automated warehouse and the coordination among multi-type and multiple resources including a group of stackers, a group of AGVs and a group of picking workstations, who cooperate to complete the outbound of the goods, an optimal coordinated scheduling scheme need be found, which achieves that the goods are assigned to the stackers, the AGVs, and the picking workstations in a certain order so that the three resources cooperate to complete the outbound process in the shortest time.

The problem involved can be summarized as an HFS problem for multiple heterogeneous resources and the scheduling includes two decisions: the equipment allocation and the processing sequence. That is, the goods are regard as the workpieces to be processed, a group of stackers, a group of AGVs and a group of picking workstations are regarded as three types heterogeneous resources, and the scheduling for each type resource is regarded as a parallel machine scheduling problem, the collaborative scheduling for three types resources is regarded as the traditional flow shop scheduling problem.

3 The collaborative scheduling model for the automated warehouse

3.1 Assumptions

Each one of the goods is in a unit of one pallet during the operation.

The inventory situation in each aisle is the same, that is, for each one of the goods, any stacker can be selected to take it away from the shelves, and the processing time is the same for different stackers. But only one stacker can be selected to do the operation for each one of goods.

Each one of the goods can be delivered and picked by any AGV and any picking workstation. The processing time is the same, but only one AGV and one picking workstation can be selected to do the operation for each one of the goods.

Each stacker, AGV, and picking workstation can only process one of the goods at a time; the operations cannot be stopped once they start.

There is no limit to the capacity of the inbound and outbound buffers of the shelves and the picking workstation.

The processing time of each one of the goods on the stackers, AGVs, and picking workstations is known.

There is no shortage of goods.

Only the outbound process is considered.

3.2 The definition of fuzzy processing time

In the field of an automated warehouse, although the degree of automation is high, there are still differences in capability between different equipment and uncertainty of processing time at different moments. The processing time of stackers is influenced by its performance and the situation of goods in stock. The processing time of AGVs is mainly influenced by situation of joined machines. The processing time of picking workstations is obviously morale of operators and their skills.

In order to quantify the impact of the above uncertainty, this paper uses triangular fuzzy number (TFN) denoted by $\tilde{T} = (T^{L}, T^{M}, T^{U})$ to describe the processing time of stackers, AGVs, picking workstations, and the fuzzy completion time of every goods on the three resources can be obtained with the scheduling and the operation of its fuzzy processing time, which is a time range and more in line with the characteristic of the actual working time; and the fuzzy processing time has considered the flexibility to deal with the impact of uncertain factors, which more satisfies operators and managers.

3.3 Formulation of the model

The fuzzy processing time is known, and this paper uses a vector as the solution of the scheduling model, and uses the List Scheduling (LS) algorithm [14] to transform the vector into a feasible scheduling scheme. In detail, a vector is used to indicate the order and according to it, the goods are assigned to the stackers. Then it is converted into a complete scheduling solution with the “First Come First Serve” (FCFS) principle. A recursive mathematical model as shown as Equations. (1) and (9) is established.

Objective: Minimize the maximum fuzzy completion time of outbound goods on the three types resources. $min {\tilde{Z}}$ (1) Constraints: $\tilde{Z} = max_{i = 1, 2, . . ., n} {\tilde{C}}_{Q_{3} (i), 3}$ (2) ${\tilde{C}}_{Q_{1} (i), 0} = 0 i = 1, 2, . . ., n$ (3) $Q_{j} = \underset{i = 1, 2, . . ., n}{sort} {{\tilde{C}}_{Q_{j - 1} (i), j - 1}} j = 2, 3$ (4) $\begin{matrix} {\tilde{C}}_{Q_{j} (i), j} = {\tilde{C}}_{Q_{j} (i), j - 1} + {\tilde{T}}_{Q_{j} (i), j} \\ i = 1, 2, . . ., m_{j}; j = 1, 2, 3 \end{matrix}$ (5) ${\tilde{MI}}_{i, j} = {\tilde{C}}_{Q_{j} (i), j} i = 1, 2, . . ., m_{j}; j = 1, 2, 3$ (6) $\begin{matrix} {\tilde{C}}_{Q_{j} (i), j} = max {{\tilde{C}}_{Q_{j} (i), j - 1}, min_{k = 1, 2, . . ., m_{j}} {{\tilde{MI}}_{k, j}}} + \\ {\tilde{T}}_{Q_{j} (i), j} i = m_{j} + 1, m_{j} + 2, . . ., n; j = 1, 2, 3 \end{matrix}$ (7) $\begin{matrix} {MN}_{j} = arg min_{k = 1, 2, . . ., m_{j}} {{\tilde{MI}}_{k, j}} \\ i = m_{j} + 1, m_{j} + 2, . . ., n; j = 1, 2, 3 \end{matrix}$ (8) $\begin{matrix} {\tilde{MI}}_{{MN}_{j}, j} = {\tilde{C}}_{Q_{j} (i), j} \\ i = m_{j} + 1, m_{j} + 2, . . ., n; j = 1, 2, 3 \end{matrix}$ (9)

The meanings of the notations are as follows:

i: the index of the goods, i = 1, 2, 3, . . . , n, there are n goods in one outbound order.

j: the index of the resource type, j = 1, 2, 3, j = 1 stands for the stacker, j = 2 stands for the AGV, j = 3 stands for the picking workstation.

m_j: the number of the j - th type resource.

$\tilde{Z}$ : the maximum fuzzy completion time of all goods on the outbound operations, which is referred to as the fuzzy completion time, and it’s a TFN.

Q_j: the order in which the goods are assigned to the j - th type resource.

Q_j (i): the i-th goods in Q_j.

MN_j: the index of the earliest available equipment of the j - th type resource.

${\tilde{T}}_{Q_{j} (i), j}$ : the fuzzy processing time of the Q_j (i) on the j - th type resource, which is a TFN denoted by ${\tilde{T}}_{Q_{j} (i), j} = (T_{Q_{j} (i), j}^{L}, T_{Q_{j} (i), j}^{M}, T_{Q_{j} (i), j}^{U})$ .

${\tilde{MI}}_{k, j}$ : the fuzzy time that equipment k of the j - th type resource enters idle state, which is a TFN.

${\tilde{C}}_{Q_{j} (i), j}$ : the fuzzy completion time of the Q_j (i) on the j - th type resource.

The meanings of the constraints are as follows:

Constraint (2) represents that the fuzzy completion time is actually the time when the picking workstations complete the picking operation for the last goods.

Constraint (3) guarantees that the completion time of all the goods on the zeroth resource is 0, that is, the time for each stacker to perform the retrieval operation is 0.

Constraint (4) represents that the order in which the goods are assigned to the j - th type resource is determined by the sequence of the completion time that each one of goods is on the (j - 1) - th type resource from small to large, that is, the first arrival goods first carry out the next operation.

Constraint (5) means that the fuzzy completion time of each one of the first to m_j - th goods in Q_j on the j - th type resource is the sum of the fuzzy completion time of it on last type resource and the fuzzy processing time of it on this type resource.

Constraint (6) ensures that the equipment who is assigned to each one of the first to m_j - th goods in Q_j immediately enters idle state when it completes the operation.

Constraint (7) represents that the fuzzy completion time of each one of the (m_j + 1) - th to n-th goods in Q_j on the j - th type resource is the sum of the fuzzy processing time of it on this type resource and the maximum value of the fuzzy completion time of it on last type resource and the fuzzy time for the earliest equipment in idle state to enter idle state.

Constraint (8) represents the index of the equipment who is assigned to Q_j (i).

Constraint (9) ensures that the equipment who is assigned to each one of the (m_j + 1) - th to n-th goods in Q_j immediately enters idle state when it completes the operation of the goods.

4 Genetic algorithm for the proposed model

The HFS problem is a NP-hard problem [15]. Genetic algorithm (GA) as a classical intelligent algorithm is widely used for solving scheduling problems. In the paper, a GA is designed to solve the collaborative scheduling model based on fuzzy processing time that this paper constructs.

4.1 The approach of ranking fuzzy numbers

Given that both $\tilde{Z}$ and the processing time are the TFN, the scheduling problem of this paper is a fuzzy decision problem. When using the GA to solve the problem, it involves the sort and comparison of $\tilde{Z}$ . This paper uses the mean and standard deviation of fuzzy numbers (e.g. Lee-Li (1988) [16]) to achieve it and evaluate the quality of different scheduling solutions, complete the judgment and selection of alternative scheduling schemes. The order of the fuzzy number with the better mean denoted by $\bar{x} (\tilde{Z})$ and the smaller standard deviation denoted by $σ (\tilde{Z})$ is higher, and according that, the $\tilde{Z}$ values of different scheduling schemes are sorted to select an optimal scheduling scheme. That is, the $\bar{x} (\tilde{Z}) + σ (\tilde{Z})$ value of one scheduling scheme is smaller, the scheme is better.

$\bar{x} (\tilde{Z})$ and $σ (\tilde{Z})$ are respectively calculated with Equations (10) and (11). $\bar{x} (\tilde{Z}) = \frac{1}{4} (Z^{L} + 2 Z^{M} + Z^{U})$ (10) $\begin{matrix} σ (\tilde{Z}) = \frac{1}{80} {3 {(Z^{L})}^{2} + 4 {(Z^{M})}^{2} + 3 {(Z^{U})}^{2} \\ - 4 Z^{L} Z^{M} - 2 Z^{L} Z^{U} - 4 Z^{M} Z^{U}} \end{matrix}$ (11)

4.2 The step of the algorithm

Step 1: Randomly generate an initial population whose size is Pop, and set the iteration counter “gen=1”.

Step 2: Solve $\tilde{Z}$ , $\bar{x} (\tilde{Z})$ and $σ (\tilde{Z})$ of each individual in the population. Base on them, the fitness function value of $f (\tilde{Z})$ is calculated.

Step 3: Determine if the iteration counter has reached the maximum number of iterations given of G_max. If it is reached, the individual with the best fitness function values in all generations is output and the algorithm stops executing, otherwise continue to execute step 4.

Step 4: According to the value of the fitness function and the method of roulette selection, selecting individuals to perform the operation of crossover and mutation, and thereby generating a new population. Then the iteration counter is updated of “gen=gen+1”and return to execute Step 2 for a loop.

4.3 The encoding and decoding

Encoding: According to the collaborative model established in this paper, the chromosome of the GA is designed as the priority in which the goods are assigned to the stackers. The process of encoding is to encode the priority, and the smaller the number in the chromosome, the higher the priority it represents. For example, a chromosome is denoted by “{6, 5, 3, 2, 4, 1}”, which represent a priority of six outbound goods are assigned to the stackers. The sixth gene in the chromosome is 1, which means that the sixth of the goods is first assigned to the stacker for the retrieval operation, and the fourth gene in the chromosome is 2, which indicates that the fourth of the goods is assigned to the stacker by the second, and so on.

Decoding: The List Scheduling algorithm is used to decode the chromosomes to obtain the equipment allocation and the processing sequence. The specific process is as follows:

The chromosome determines the assignment order of the outbound goods assigned to the stackers for the retrieval operation. In order to reduce the waiting time and improve the efficiency of the entire system, the order in which they are assigned to the AGVs and the picking workstation is determined by the FCFS principle, that is, which is obtained by sorting the fuzzy completion time of the operation the goods on the stackers or AGVs. For example, assume that the sixth of the goods is first taken out of the shelves by one stacker and sent to the outbound buffer, then it will be first assigned to the idle AGV to send it to the picking workstations. In addition, when assigned to the idle equipment, the equipment that first entered the idle state is selected by sorting the time of the equipment enters idle.

After that, according to the equipment allocation and the processing sequence, the start and end time of the operation on each type resource for every one of the goods can be obtained.

4.4 Fitness function

Due to the fact that the GA needs to compare, sort, and select the individuals in the population according to the value of the fitness function. Following the higher order of the fuzzy numbers with better average and smaller standard deviation described in Section 4.1, the fitness function is designed as shown in Equation (12). $f (\tilde{Z}) = \frac{1}{\bar{x} (\tilde{Z}) + σ (\tilde{Z})}$ (12)

4.5 Crossover and mutation

In this paper, the Order Crossover (OX) is used to achieve the crossover of the chromosomes to obtain a new priority of the goods assigned to the stackers. Figure 2 is an example of the crossover.

Fig. 2

An example of the crossover.

When performing the mutation operation, a new individual is generated by randomly exchanging the genes at two positions on the old chromosome. Figure 3 is an example of the mutation.

Fig. 3

An example of the mutation.

5 A numerical example

5.1 Example design

The layout of an AS/RS automated warehouse is shown in Fig. 1, including six aisles with single deep shelves, 6 stackers to store and retrieve the goods in units of pallets, 2 AGVs to the deliver the goods between the stackers and the picking workstations, 2 picking workstations to do the picking operation of the manual picking, packaging, confirmation, etc.

Suppose that there are 20 outbound goods to be retrieved from the shelves and sent to picking workstations to perform the picking operation. The set of the goods is denoted as “O = {O₁, O₂, O₃, O₄, O₅, O₆, O₇, O₈, O₉, O₁₀, O₁₁, O₁₂, O₁₃, O₁₄, O₁₅, O₁₆, O₁₇, O₁₈, O₁₉, O₂₀}”.

The fuzzy processing time is determined by the following method:

The processing time of each one of the goods on the stackers denoted as T_Q₁(i),1 is related to its storage location. T_Q₁(i),1 is randomly generated and then is converted into a TFN denoted as ${\tilde{T}}_{Q_{1} (i), 1}$ , whose the most likely value denoted as $T_{Q_{1} (i), 1}^{M}$ is T_Q₁(i),1, the most optimistic value is randomly generated in the range [0.9T_Q₁(i),1, T_Q₁(i),1] and the most pessimistic value is randomly generated in the range [T_Q₁(i),1, 1.1T_Q₁(i),1].

Similarly, the processing time on the AGVs denoted as T_Q₂(i),2 is related to the occupation situation, the length of the path and the situation of joined machines during the operation; the processing time on the picking workstations denoted as T_Q₃(i),3 is related to the operation required for the goods, the skill of the operator, etc. T_Q₂(i),2 and T_Q₃(i),3 are randomly generated, which respectively obeys the normal distribution N (120, 10) and N (170, 25), then they are converted into TFNs denoted as ${\tilde{T}}_{Q_{2} (i), 2}$ , ${\tilde{T}}_{Q_{3} (i), 3}$ .

According to that, the fuzzy processing time of each one of the goods in the O on the stackers, the AGVs, the picking workstations is generated shown in Table 1. Besides, assume that the assumptions in Section 3.1 are satisfied.

Table 1
The fuzzy processing time of each cargo in the order O (unit: second)

Index of the goods $T_{Q_{1} (i), 1}^{L}$ $T_{Q_{1} (i), 1}^{M}$ $T_{Q_{1} (i), 1}^{U}$ $T_{Q_{2} (i), 2}^{L}$ $T_{Q_{2} (i), 2}^{M}$ $T_{Q_{2} (i), 2}^{U}$ $T_{Q_{3} (i), 3}^{L}$ $T_{Q_{3} (i), 3}^{M}$ $T_{Q_{3} (i), 3}^{U}$

1 246 253 263 116 123 134 179 177 192

2 132 137 138 131 134 142 147 154 158

3 75 76 77 116 124 127 161 182 192

4 198 214 231 120 129 141 158 168 190

5 185 195 210 102 104 110 154 147 174

6 278 296 304 120 127 129 167 174 182

7 239 264 282 137 141 155 166 163 188

8 268 284 297 117 125 129 162 160 184

9 135 140 141 100 105 105 137 152 173

10 117 125 135 115 118 123 165 172 179

11 95 98 100 115 115 120 111 124 144

12 219 240 242 120 124 126 146 160 165

13 381 423 441 118 124 126 156 156 184

14 249 258 277 122 124 135 143 147 168

15 132 138 140 110 116 124 169 186 222

16 257 267 270 108 114 120 148 152 172

17 100 110 111 113 114 121 163 184 213

18 79 86 87 122 129 132 197 194 199

19 237 257 266 97 101 106 162 166 177

20 128 138 141 112 118 125 173 177 191

Index of the goods	$T_{Q_{1} (i), 1}^{L}$	$T_{Q_{1} (i), 1}^{M}$	$T_{Q_{1} (i), 1}^{U}$	$T_{Q_{2} (i), 2}^{L}$	$T_{Q_{2} (i), 2}^{M}$	$T_{Q_{2} (i), 2}^{U}$	$T_{Q_{3} (i), 3}^{L}$	$T_{Q_{3} (i), 3}^{M}$	$T_{Q_{3} (i), 3}^{U}$
1	246	253	263	116	123	134	179	177	192
2	132	137	138	131	134	142	147	154	158
3	75	76	77	116	124	127	161	182	192
4	198	214	231	120	129	141	158	168	190
5	185	195	210	102	104	110	154	147	174
6	278	296	304	120	127	129	167	174	182
7	239	264	282	137	141	155	166	163	188
8	268	284	297	117	125	129	162	160	184
9	135	140	141	100	105	105	137	152	173
10	117	125	135	115	118	123	165	172	179
11	95	98	100	115	115	120	111	124	144
12	219	240	242	120	124	126	146	160	165
13	381	423	441	118	124	126	156	156	184
14	249	258	277	122	124	135	143	147	168
15	132	138	140	110	116	124	169	186	222
16	257	267	270	108	114	120	148	152	172
17	100	110	111	113	114	121	163	184	213
18	79	86	87	122	129	132	197	194	199
19	237	257	266	97	101	106	162	166	177
20	128	138	141	112	118	125	173	177	191

The parameters of the GA are set as: the population size of Pop is 100, the crossover probability of P_c is 0.5, the mutation probability of P_m is 0.02, the maximum generation of G_max is 100.

5.2 Example results

The MATLAB tool and the GA are used to solve the collaborative scheduling model of this paper. The algorithm is run and the best individual of all generations is selected. The better feasible solution got is “{11, 14, 19, 12, 15, 20, 3, 8, 17, 9, 6, 10, 2, 7, 4, 13, 5, 16, 18, 1}”, which is an optimal individual obtained in the 14th generation (100 generations) in the certain scenario.

The optimal scheduling solution is not necessarily a global optimal solution, but can be used as a basis for scheduling. The first number in the solution is 11, indicating that the first of the outbound goods O is ranked 11th to be assigned to the stackers for the retravel operation. The $\tilde{Z}$ of the solution is (1861,1933,2046) (unit: second), the most likely value of the $\tilde{Z}$ denoted as Z^M is 1933 seconds, and the $\bar{x} (\tilde{Z})$ is 1944 seconds.

According to the rules of the encoding and decoding, the equipment allocation and the processing sequence of the solution can be obtained, which are as shown in Table 2.

Table 2
The equipment allocation and the processing sequence

Equipment The equipment allocation and the processing sequence

Stacker 1 O₂₀ → O₁₀ → O₁ → O₆

Stacker 2 O₁₃ → O₁₈ → O₁₉

Stacker 3 O₇ → O₄ → O₉

Stacker 4 O₁₅ → O₁₂ → O₂ → O₃

Stacker 5 O₁₇ → O₈ → O₅

Stacker 6 O₁₁ → O₁₄ → O₁₆

AGV 1 O₁₁ → O₂₀ → O₁₀ → O₁₄ → O₈ → O₄

→O₂ → O₃ → O₁₆ → O₆

AGV 2 O₁₇ → O₁₅ → O₇ → O₁₂ → O₁₃ → O₁₈

→O₁ → O₅ → O₉ → O₁₉

Picking worstation 1 O₁₁ → O₂₀ → O₁₀ → O₁₄ → O₈ → O₄ → O₂

→O₅ → O₉ → O₁₆ → O₆

Picking worstation 2 O₁₇ → O₁₅ → O₇ → O₁₂ → O₁₃ → O₁₈

→O₁ → O₁₉

Equipment	The equipment allocation and the processing sequence
Stacker 1	O₂₀ → O₁₀ → O₁ → O₆
Stacker 2	O₁₃ → O₁₈ → O₁₉
Stacker 3	O₇ → O₄ → O₉
Stacker 4	O₁₅ → O₁₂ → O₂ → O₃
Stacker 5	O₁₇ → O₈ → O₅
Stacker 6	O₁₁ → O₁₄ → O₁₆
AGV 1	O₁₁ → O₂₀ → O₁₀ → O₁₄ → O₈ → O₄
	→O₂ → O₃ → O₁₆ → O₆
AGV 2	O₁₇ → O₁₅ → O₇ → O₁₂ → O₁₃ → O₁₈
	→O₁ → O₅ → O₉ → O₁₉
Picking worstation 1	O₁₁ → O₂₀ → O₁₀ → O₁₄ → O₈ → O₄ → O₂
	→O₅ → O₉ → O₁₆ → O₆
Picking worstation 2	O₁₇ → O₁₅ → O₇ → O₁₂ → O₁₃ → O₁₈
	→O₁ → O₁₉

A Gantt chart obtained according to $T_{Q_{j} (i), j}^{M}$ of the solution is shown in Fig. 4.

Fig. 4

The Gantt chart obtained according to $T_{Q_{j} (i), j}^{M}$ of the solution.

As can be seen from the Fig. 4, the ratio of the operation time of the three types resources, i.e. the stackers, AGVs and picking workstations, to Z^M can be observed and it is found that the ratio of the processing time of the picking workstations to Z^M is 88.9%, which is the largest; the next one is the ratio of the AGVs, which is 63.3%; the smallest is the ratio of the stackers, which is 41.8%. It is concluded that in the outbound processing, the total operation time that the AGVs and the picking workstations process the goods is longer, and the resources of AGVs and picking workstations are easy to become the system capacity bottlenecks.

6 Impact analysis of resource allocation on Z^M and ρ

In view of the fact that the ability of each type resource is determined and difficult to change, this paper introduces the capability coordination degree denoted by ρ as an evaluation index [17], which describes the degree of various types resources capability coordination in the automated warehouse from perspective of the whole system. The most likely time of the fuzzy completion time Z^M is extracted to measure the effect of the scheduling; the initial investment denoted by F of resources (equipment) is used to describe the initial investment economy of various resources. The influence level of resource allocation schemes on Z^M, ρ and F is revealed through the following numerical experiments.

(1) The calculation method of ρ and F

ρ is calculated with Equations (13) and (14). The value range of ρ is [0,1], and the larger the value of ρ is, the better the coordination of various types resources operation ability. $ρ = \frac{\sum_{j = 1}^{s - 1} {[\frac{4 E_{j} • E_{j + 1}}{{(E_{j} + E_{j + 1})}^{2}}]}^{p}}{s - 1}$ (13) $E_{j} = \frac{\bar{{OT}_{j}}}{{ET}_{j} - {ST}_{j}} = \frac{\sum_{i = 1}^{n} T_{O_{i}, j}}{n ({ET}_{j} - {ST}_{j})}$ (14)

The meanings of the notations are as follows:

E_j: The capability of the j - th type resource.

s: The number of resource type included in the calculated capability coordination degree

p: The adjustment coefficient; p ⩾ 2; the p value affects the hierarchy of the calculated capability coordination degree, which depends on the actual system. This paper takes p = 6.

ST_j: The moment when the j - th resource first starts the operation.

ET_j: The moment when the j - th resource finally completes the operation.

$\bar{{OT}_{j}}$ : The average processing time of the outbound goods on the j - th type resource.

T_{O_i,j}: The processing time of the outbound goods O_i on the j - th type resource; this paper takes the most likely value of the triangle fuzzy processing time.

F is calculated with Equation (15). The cost of the initial investment in the k-th equipment of the j - th type resource is denoted by p_jk. $F = \sum_{j = 1}^{3} \sum_{k = 1}^{m_{j}} p_{jk}$ (15)

(2) Numerical experiments design

The resource allocation scheme of the automated warehouse: The number of the stacker denoted by m₁ is 6; the number of the AGV denoted by m₂ varies from 2 to 6; the number of the picking workstation denoted by m₃ varies from 2 to 6. There are 25 schemes and the scheduling scheme, Z^M and ρ of each resource allocation scheme is obtained by the GA designed in this paper. Each scheme is run 100 times and the average results are recorded for the analysis in order to reduce possible bias caused by the randomness of the GA.

(3) Numerical experiments results

The Z^M, ρ and F of the different resource allocation schemes are shown in Table 3 (the unit of F is ten thousand CNY, the unit of Z^M is second), and the distribution of ρ and Z^M is shown in Figs. 5 and 6.

Fig. 5

The distribution of Z^M.

Fig. 6

The distribution of ρ.

As can be seen from Table 3, the initial investment F of different resource allocation schemes is proportional to the unit purchase cost of various types resources and the number of purchases, so it is not described in detail. Considering Z^M, ρ, and F together, the resource allocation scheme 12 is optimal. At this time, the number of the stacker is 6, the number of the AGV is 3, and the number of the picking workstation is 4.

Table 3

The Z^M, ρ and F of the different resource allocation schemes

Group	Index	m₁	m₂	m₃	F	Z^M	ρ
Group 1	1	6	2	2	400	1921.2	0.743
	2	6	3	2	465	1921.0	0.807
	3	6	4	2	530	1918.7	0.805
	4	6	5	2	595	1923.2	0.804
	5	6	6	2	660	1921.3	0.802
Group 2	6	6	2	3	415	1488.2	0.715
	7	6	3	3	480	1394.8	0.905
	8	6	4	3	545	1395.8	0.933
	9	6	5	3	610	1392.7	0.933
	10	6	6	3	675	1388.6	0.931
Group 3	11	6	2	4	430	1477.3	0.701
	12	6	3	4	495	1149.0	0.888
	13	6	4	4	560	1119.0	0.919
	14	6	5	4	625	1116.5	0.923
	15	6	6	4	690	1117.8	0.924
Group 4	16	6	2	5	445	1477.4	0.700
	17	6	3	5	510	1105.1	0.879
	18	6	4	5	575	1039.7	0.911
	19	6	5	5	640	1033.4	0.916
	20	6	6	5	705	1033.4	0.919
Group 5	21	6	2	6	460	1478.6	0.710
	22	6	3	6	525	1105.6	0.878
	23	6	4	6	590	1023.9	0.908
	24	6	5	6	655	1009.8	0.911
	25	6	6	6	720	1001.2	0.919

6.1 Impact analysis of resource allocation on Z^M

It is found by observing the experiments from group1 to group 5 that the increase of the number of AGVs is not significant in reducing Z^M when the number of the stacker and the picking workstation is constant. Taking the group 2 as an example, when there are 6 stackers and 3 picking workstations, and the number of the AGV is increased from 2 to 6, Z^M varies between [1388.6,1488.2], and the standard deviation is 38.1701, the range of the improvement degree of Z^M is [6.21%,6.69%].

A significant variety and a point at which Z^M is the largest can be found by analyzing the 1–5 group experiments. That is, when the number of the AGV in each group is 2, the value of Z^M is the largest, which means the AGV is the bottleneck of the system capacity. For the group2, when m₁ is 6, m₂ is 3 and m₃ is 2, Z^M is 1488.2 seconds, it is the longest, and the AGVs is the bottleneck. At this time, the overall efficiency of the system is not improved with the number of the picking workstation increasing.

Considering (2), when the schemes 1, 6, 11, 16, and 21 in which m₂ is 2 are not considered, that is, the AGV is not as the capability bottleneck, the mean of the Z^M of other schemes in the group1 to group5 is 1920.9, 1393.0, 1125.6, 1055.7, and 1035.1, respectively. The reduction of Z^M is significantly with the increase of the picking workstation number and the range of the improvement degree is [37.9%,85.6%].

Considering Z^M and F, the resource allocation scheme 17 is optimal. At this time, the number of the stacker is 6, the number of the AGV is 3, and the number of the picking workstation is 5.

6.2 Impact analysis of resource allocation on ρ

The impact of the resource allocation on ρ is similar to that on Z^M.

The increase in the number of the AGVs is not significant in improve ρ when the number is more than 2 and the number of other resources is constant. For the group2, when m₁ is 6 and m₃ is 3, and m₂ is increased from 3 to 6, ρ varies between [0.905,0.933], and the standard deviation of ρ is 0.0117, the range of the improvement degree of ρ is [2.85%,3.03%]. It can be seen that when the number of the AGV reaches a certain level, the contribution of its increase to the promotion of ρ is not significant.

When the number of the AGVs in each group is 2, the value of ρ is the smallest, which means the AGV is the bottleneck resource of the system capacity. For the group2, when m₁ is 6, m₂ is 3 and m₃ is 2, ρ is 0.715, it is the smallest in the group, and the AGVs is the bottleneck. At this time, ρ is not improved with the number of the picking workstation increasing.

When the schemes 1, 6, 11, 16, and 21 are not considered, the mean of the ρ of the group 1 to group 5 is 0.804, 0.926, 0.913, 0.906, and 0.904, respectively, and when m₃ is increasing from 3 to 6, ρ slightly decreases, that is, when the number of the picking workstation reaches to a certain level, the contribution to the promotion ρ is not significant.

In the automated warehouse scenario, the ρ of the scheme 8, in which m₁ is 6, m₂ is 3 and m₃ is 2, is the largest.

7 Conclusion

This paper studies the collaborative scheduling problem of the outbound process for the stackers, AGVs and picking workstations with fuzzy processing time in an automated warehouse scene based on the HFS problem. A recursive mathematical model is built with the triangular fuzzy number used to represent the processing time of the equipment, a vector used to represent the solution of the scheduling model and the List Scheduling algorithm used to convert the vector to the complete scheduling scheme. And a GA is designed by combining the method of ranking fuzzy number operation and vector coding method, and a feasible scheduling solution is obtained with that.

The instructive conclusions obtained are as follows:

In the automated warehouse, the stackers, AGVs, and picking workstations can be regarded as three types parallel machines sub-system with different resource attributes in the intelligent logistic storage system, and the coordination scheduling problem for the three types resources is abstracted into the multi-type and multiple resources HFS problem, which provides a new path to solving the difficulty in modeling the complex engineering problems.

The TFN is used to represent the fuzzy processing time of various resources, and the single-objective HFS problem in the traditional determined environment is extended to the fuzzy environment of the automated warehouse operation in the real scene. The scheduling solution fully considers the influence of the uncertainty factors on the actual processing time of various resources in the automated warehouse, and the completion time is the shortest with the scheduling scheme under these influences. The collaborative scheduling scheme based on fuzzy processing time can realize the tasks assignment for the multi-type and multiple resources and the arrangement of the tasks processing sequence, which enables the manager to better grasp the time range of scheduling, and improves the overall efficiency of the automated warehouse by system operation flexibility and scheduling flexibility.

Observing the ratio of the processing time of the three types resources (the stackers, AGVs and picking workstations) to the most likely system operation completion time of Z^M, the proportion of the processing time of the picking workstations is 88.9%, which is more frequently called for the delivery operation and easier to become the system bottleneck than the stackers and AGVs, which mainly due to the lean requirements of the quantity, quality and operation order of the outbound goods, and the high requirements for the operation ability of the picking workstations. The AGVs is as a mobile resource and its proportion is 63.3%; the increase of the number has an impact on the overall efficiency and capacity coordination degree of the system, but it is not significant, which is because that the AGVs has the function of connecting between the stackers and the picking workstations, and its performance is limited by the output capabilities of the upstream and downstream recourses.

This paper analyzes the coordination scheduling problem for multi-type and multiple resources in the outbound process of an automated warehouse from whole the system perspective, and capability coordination degree is used to measure the coordination level of capabilities among different types of resources, which provides a new idea for optimizing the operation of automated warehouse. Through the sensitivity analysis of each resource allocation scheme to Z^M, ρ and F, it is found that the optimal resource allocation is closely related to the coordination of system capabilities, and simply increasing the amount of resources and paying no attention to structural configuration of recourses will not necessarily lead to better system efficiency.

Footnotes

Acknowledgment

This research is supported by Jilin Province Transportation Science and Technology Project of China (No. 20160112); R&D program of Pan Asia Technical Automotive Center (No. 20180528).

References

Kung

, Kobayashi

, Higashi

, Sugi

and Ota

, Order scheduling of multiple stacker cranes on common rails in an automated storage/retrieval system, International Journal of Production Research 52(4) (2014), 1171–1187.

Yuan

, Wang

, Sun

and Li

, Research on the Task Scheduling of “Goods to Picker” Order Picking System Based on Logistics AGV, Operations Research and Management Science 27(10) (2018), 133–138.

Liu

, Research on Scheduling Policy of Automated Warehouse System, in: Proceedings of the 2nd International Conference on Computer Science and Application Engineering, (2018).

Jiang

, Research on joint operation of the stacking crane and AGV transportation of a tobacco formula raw material automatic storage and retrieval system, Master’s Thesis, Beijing Wuzi University, (2017).

Homayouni

S.M.

, Tang

S.H.

and Motlagh

, A genetic algorithm for optimization of integrated scheduling of cranes, vehicles, and storage platforms at automated container terminals, Journal of Computational and Applied Mathematics 270 (2014), 545–556.

Tian

, Wang

, Chen

and Fan

, Collaborative scheduling of QCs, L-AGVs and ARMGs under mixed loading and unloading mode in automated terminals, Journal of Shanghai Maritime University 39(3) (2018), 14–21.

Yang

, Optimization of L-AGVTask Scheduling under the Dual-Cycling Operation at Automated Terminals, Master’s Thesis, Jilin University, (2019).

Cinar

, Oliveira

J.A.

, Topcu

Y.I.

and Pardalos

P.M.

, Scheduling the truckload operations in automated warehouses with alternative aisles for pallets, Applied Soft Computing 52 (2017), 566–574.

Guo

, Jiang

, Chu

and Geng

, Study of Scheduling of Parallel Multi-task Picking Based on Limited Working Area, Industrial Engineering and Management (3) (2012), 102–107.

10.

Shen

and Guo

, Uncertain flexible flow shop scheduling problem subject to breakdowns, Journal of Intelligent & Fuzzy Systems 32(1) (2017), 207–214.

11.

Lei

, A genetic algorithm for flexible job shop scheduling with fuzzy processing time, International Journal of Production Research 48(10) (2010), 2995–3013.

12.

, Xu

and Li

, Single machine due window assignment scheduling problem with precedence constraints and fuzzy processing times, Journal of Intelligent & Fuzzy Systems 34(6) (2018), 4301–4314.

13.

Jia

, Yan

, Leung

J.Y.T.

, Li

and Chen

, Ant colony optimization algorithm for scheduling jobs with fuzzy processing time on parallel batch machines with different capacities, Applied Soft Computing Journal 75 (2019), 548–561.

14.

Ouz

, Zinder

, Dob

V.H.

, Janiak

and Lichtenstein

, Hybrid flow-shop scheduling problems with multiprocessor task systems, European Journal of Operational Research 152(1) (2004), 115–131.

15.

Hoogeveena

J.A.

, Lenstraa

J.K.

and Veltmanb

, Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard, European Journal of Operational Research 89(1) (1996), 172–175.

16.

Lee

E.S.

and Li

R.J.

, Comparison of fuzzy numbers based on the probability measure of fuzzy events, Computers and Mathematics with Applications 15(10) (1988), 887–896.

17.

Zhang

, Research on Capacity Coordination of Facilities and Equipment of Railway Container Terminal, Master’s Thesis, Beijing Jiaotong University, (2015).