自動化外文文獻翻譯-在帶貨盤替代通道的自動化倉庫中安排整車運作【中文8400字】 【PDF+中文WORD】,中文8400字,PDF+中文WORD,自動化外文文獻翻譯-在帶貨盤替代通道的自動化倉庫中安排整車運作【中文8400字】,【PDF+中文WORD】,自動化,外文,文獻,翻譯,帶貨盤,替代,通道,倉庫,安排 Contents lists available at ScienceDirect Applied Soft Computing j ournal homepage: www.elsevier.com/locate/asoc Applied Soft Computing 52 (2017) 566–574 Scheduling the truckload operations in automated warehouses with alternative aisles for pallets Didem Cinara,b,?, José António Oliveirac, Y. Ilker Topcua, Panos M. Pardalosb a Department of Industrial Engineering, Faculty of Management, Istanbul Technical University, Istanbul, Turkey b Department of Industrial and Systems Engineering, Faculty of Engineering, University of Florida, Gainesville, United States c ALGORITMI Research Centre, University of Minho, Braga, Portugal a r t i c l e i n f o a b s t r a c t Article history: Received 5 June 2015 Received in revised form 27 June 2016 Accepted 13 October 2016 Available online 19 October 2016 Keywords: Automated storage and retrieval systems Truckload operations scheduling Flexible job shop scheduling Genetic algorithms In this study, the scheduling of truck load operations in automated storage and retrieval systems is investigated. The problem is an extension of previous ones such that a pallet can be retrieved from a set of alternative aisles. It is modelled as a ?exible job shop scheduling problem where the loads are considered as jobs, the pallets of a load are regarded as the operations, and the forklifts used to remove the retrieving items to the trucks are seen as machines. Minimization of maximum loading time is used as the objective to minimize the throughput time of orders and maximize the ef?ciency of the warehouse. A priority based genetic algorithm is presented to sequence the retrieving pallets. Permutation coding is used for encoding and a constructive algorithm generating active schedules for ?exible job shop scheduling problem is applied for decoding. The proposed methodology is applied to a real problem arising in a warehouse installed by a leading supplier of automated materials handling and storage systems. ? 2016 Elsevier B.V. All rights reserved. 1. Introduction Automated storage and retrieval system (AS/RS) is a warehous- ing system that uses mechanic devices for the storage and retrieval of products in both distribution and production environments [1,2]. Automatic cranes move through aisles between racks to put the items on the racks and retrieve those items from storage to the col- lector for ful?lling the customer orders. AS/RS is fully automated, because no intervention of an operator is needed for handling the pallets [2]. When an order is received for an item, a stacker crane retrieves the pallet from its storage location and carries it to the col- lector at the top of the aisle that is a gravity roller conveyor. At the end of the roller conveyor, the conveyed pallet is picked up using a forklift truck. High space utilization, improved material ?ow, and improved inventory control are some of the advantages of AS/RS [3]. The best utilization from such a system can be succeed by optimal design and optimal scheduling of the system. Warehouse scheduling optimization is a combinatorial opti- mization problem which cannot be solved with exact algorithms in reasonable computational time for high dimensional instances. ? Corresponding author at: Department of Industrial Engineering, Faculty of Man- agement, Istanbul Technical University, Istanbul, Turkey. E-mail addresses: cinard@itu.edu.tr (D. Cinar), zan@dps.uminho.pt (J.A. Oliveira), topcuil@itu.edu.tr (Y. Ilker Topcu), pardalos@u?.edu (P.M. Pardalos).  Because of the high complexity of the problem, simulation and metaheuristics have been widely used in warehouse scheduling optimization [4]. A detailed literature review about the method- ologies developed for AS/RS design and scheduling is given in Section 3. In this study, the scheduling of truck load operations arising in AS/RS is investigated. The problem is modelled as a ?exible job shop scheduling problem (FJSP) by considering the loads as jobs and pallets of a load as its operations. The forklifts which are used for transportation of pallets from collectors to trucks are considered as machines. The main contributions of this paper are twofold: (1) scheduling of truck load operations is modelled as a ?exible job shop scheduling problem, (2) a real problem arising in an AS/RS warehouse installed by a leading supplier of automated materials handling and storage systems is solved by using a priority based genetic algorithm and the effect of aisle selection ?exibility is inves- tigated. To the best of the authors’ knowledge, this work is the ?rst time that the FSJP is used to model the retrieving operation of pallets in an AS/RS warehouse. The paper is organized as follows. Section 2 provides a brief explanation on investigated automated storage system. In Sec- tion 3, a literature review on scheduling of truck load operations is given. Section 4 represents a mixed integer programming (MIP) formulation for a truckload operations scheduling problem in AS/RS and discusses the modelling of the problem as a ?exible job shop scheduling problem. Section 5 presents the devoted methodology. http://dx.doi.org/10.1016/j.asoc.2016.10.013 1568-4946/? 2016 Elsevier B.V. All rights reserved. D. Cinar et al. / Applied Soft Computing 52 (2017) 566–574 567 Fig. 1. Schema of the warehouse. Section 6 gives the computational results for a real life AS/RS ware- house problem. Finally, Section 7 presents the conclusion. 2. Storage system The methodology proposed in this study is applied to an AS/RS warehouse in Italy which works as a distribution center. Products are stored by the warehouse and loaded to the trucks to ful?ll the orders of customers. Routes of the trucks, which are known in advance, are determined considering the delivery deadline of cus- tomer orders. The warehouse consists of eleven aisles constituted by pallet racks with the capacity of 40,000 pallets. An automatic stacker crane or S/R machine works in each aisle to move the pallets from their respective rack to the collector at the beginning of the aisle. Forklifts transport the pallets to the trucks. The warehouse has 13 docking bays to load the trucks. A scheme of the loading process in this warehouse is shown in Fig. 1. Warehouse Planning System (WPS) and Warehouse Manage- ment System (WMS) are used to operate the warehouse. Daily planning of loadings for each truck is executed by WPS. The sequence of retrieving pallets and the movement of S/R machines and forklifts are determined by WMS. Approximately one hun- dred loads are retrieved per day by a truck. Each truck has its own delivery time which is considered by WPS and loading must not be delayed. In the strategy de?ned for the WPS, the whole set of loads are divided into subsets called batches. Loads in a batch are processed simultaneously. Loading of a batch cannot be started before the loads of previous batch are ?nished. The size of a batch is determined with respect to delivery deadlines and the number of docking bays. A standard daily plan includes 15–20 batches with 6–13 loads for each one. An order of a customer consists a product or a set of products that are delivered on one or more pallets. The set of products for an order is known in advance, and it is available in the warehouse. A truck load consists of a set of pallets transported for one or more clients. The sequence of loading pallets on the truck is determined by WMS with LIFO (Last In First Out) rule. Since the sequence of pallets in a load is predetermined and cannot be changed, precedence relations exist between pallets of a load. The pallets of a load can be retrieved from any aisle. To facilitate the assignment of the trucks to the docking bays, several pallets are placed in different aisles to reduce the time of load prepara- tion, allowing a pallet to be selected in an aisle that is close to the truck and respecting the FEFO (First-Expired-First-Out) rule. The S/R machine is programmed to retrieve the pallets from the corresponding aisle. We assume that each forklift can work for only one aisle. After a forklift receives a pallet from its own aisle, it can carry the pallet to any truck. For safety reasons, more than one forklift cannot be allowed to place pallets in a truck at the same time. So, one load should receive one pallet at a certain time. After a pallet is loaded to the truck, the forklift returns to its aisle and communicates to WMS that it is available for a new transportation. Then the next pallet for the same load is programmed. A forklift can receive only one pallet at each transportation. Detailed information about the analysed AS/RS warehouse can be obtained from [5]. Different sequences of pallets in a batch retrieved by S/R machines result in different processing times. An illustrative exam- ple is the following. Assume that there are 5 aisles in the warehouse represented by A1, A2, . . ., A5. The problem is planning the retriev- ing sequence of a batch including 3 loads. Each load consists of 4 pallets, which have precedence relations in advance, representing a total of 12 pallets to be retrieved in the batch. There is one forklift for each aisle to carry the pallets from the aisle to the correspond- ing truck. Although a pallet can be retrieved from several aisles, in previous studies [5,6] it was assumed that it is the WMS that previ- ously selects the pallets considering the distance to the aisle where the load is prepared. The aisle for each pallet and the processing times are given in Table 1. The aisle storing pallet j and the transportation time between related aisle and truck are shown as (Ak, t) where Ak refers the kth aisle and t is the transportation time from aisle Ak to truck. For example, the ?rst pallet of the second load must be retrieved Table 1 An illustrative example for real problem. jth pallet Load i 1 2 3 4 1 (A1 ,1) (A2 ,2) (A3 ,3) (A4 ,4) 2 (A3 ,1) (A1 ,3) (A3 ,1) (A4 ,2) 3 (A4 ,2) (A4 ,2) (A3 ,3) (A5 ,1) 568 D. Cinar et al. / Applied Soft Computing 52 (2017) 566–574 Fig. 2. Two different schedules for retrieving the pallets. from the third aisle with time 1. For convenience, the pallets were consecutively numbered from 1 to 12. Fig. 2 shows two different sequences of retrieving pallets. The numbers inside the rectangles identify the pallets. For each sequence, Fig. 2 presents the Gantt chart for the set of aisles (left side) and the Gantt chart for the set of loads (right side), which represents better the processing time of the batch. The sequences for retrieving pallets only differ at Aisle 3, where the pallet 11 is collected either after pallets 3 and 7 (Fig. 2(a)), or before pallets 3 and 7 (Fig. 2(b)). The decision when to retrieve pallet 11 produces signi?cantly different processing times for the entire batch of loads. Fig. 2(a) presents the optimal solution for this small example. 3. Literature review In an AS/RS, planning and performing of accurate loading pro- cesses are very important to meet the customer orders at the proper time [5]. Among previous studies, analysis oriented ones constituted the majority of the literature rather than those devel- oping models and techniques for warehouse design [7]. Simple heuristics and simulation techniques were used for storage and retrieval problems in automated warehousing systems. Bozer and White [8] proposed travel time models for automated S/R machines with single and dual command mode. Han et al. [9] proposed a nearest neighbour heuristic for retrieval sequencing in AS/RS with dual command cycles and used Monte Carlo simulation for eval- uation. Eben-Chaime [10] also used a nearest neighbour heuristic to sequence the retrievals. Hausman et al. [3] compared several storage assignment rules to determine the optimal storage assign- ment policy. Schwarz et al. [11] analysed both storage assignment and interleaving rules with a simulation model. Lee and Schae- fer [12] formulated the problem, which is also handled by Han et al. [9], as an assignment problem. They proposed a methodology combining the Hungarian method and the ranking algorithm for the assignment problem with the tour-checking and tour-breaking algorithms. In the last few years, besides the mathematical modeling and simulation approaches, metaheuristics have been used in these areas. Comprehensive reviews of warehouse design and control can be found in de Koster et al. [13], Gu et al. [14] and Baker and Canessa [15]. Moreover, detailed explanations of the current state of the art in AS/RS design are provided by Roodbergen and Vis [2] and Vasili et al. [16]. Manzini et al. [17] developed a multi-parametric dynamic model for a product-to-picker storage system with class- based storage allocation of products. They investigated the factors affecting the warehousing system performance. Yin and Rau [18] combined simulation and genetic algorithms for the dynamic selec- tion of sequencing rules for a class-based unit-load AS/RS. Chang et al. [19] proposed a multi-objective mathematical programming model and a genetic algorithm for the order picking of stacker cranes. Kung et al. [20] developed a dynamic programming based order scheduling methodology for the AS/RS with multiple stacker cranes on a common rail. The problem includes both assignment of orders to each crane and scheduling of cranes without collision. Brezovnik et al. [21] used a multi-objective ant colony optimization method for the storage allocation problem in an AS/RS. Based on the computational results obtained from a home appliance devices warehouse, it was shown that optimal space utilization can be achieved when the products with lower weight and height are stored at higher levels. Yang et al. [22] inferred that the speed pro?le of an S/R machine has an important effect on the optimal stor- age rack for a multi-deep AS/RS. Atmaca and Ozturk [4] proposed a mathematical programming model and a simulated annealing approach for the storage allocation and storage assignment prob- lems to minimize storage costs. Optimal solution was obtained by the proposed mathematical model for problems having up to 103 materials. Dooly and Lee [23] modelled a shift-based sequencing problem for twin-shuttle AS/RS as a minimum-cost perfect match- ing problem and presented a polynomial-time exact algorithm. Oliveira [5] and Figueiredo et al. [6] modelled the truck load operations on an AS/RS warehouse as a job shop scheduling prob- lem (JSP) with recirculation [5]. Oliveira [5] assumed identical processing times to transport pallets independently of the location D. Cinar et al. / Applied Soft Computing 52 (2017) 566–574 569 of the aisle and the truck. Figueiredo et al. [6] extended the problem by considering different processing times and solved it by genetic algorithms with random keys representation. Both Oliveira [5] and Figueiredo et al. [6] assumed that a pallet can be retrieved from one aisle previously decided by WMS, considering the proximity to the docking bay. In this study, this assumption is extended by consid- ering alternative aisles for pallets. The selection of the aisle where the pallets are retrieved is determined with truck load scheduling simultaneously. So the problem consists of both selection of an aisle to retrieve the pallet, which is currently performed by WMS, and the scheduling of pallets’ transportation from collector to truck. In this way, the bene?t of combining these two operations is inves- tigated. No study which addresses this problem as a FJSP has been encountered in the scope of this study. 4. Modelling AS/RS warehouses as FJSP In this section, a MIP formulation for the truckload operation scheduling problem is presented. We do not consider cross-docking or order picking to produce a pallet. The assumptions considered in this study are given as follows: ? an order is formed by only (complete) pallets of products that are stored in the warehouse. ? an S/R machine is faster to put a pallet on the collector than a forklift to remove a pallet and an S/R machine operates in advance of the forklift, ? a collector works as a buffer with capacity for several pallets, ? the ?ow of pallets in the collector (gravity roller conveyor) follows the FIFO rule, ? an S/R machine takes zero units of time to put a pallet in the collector. The notation used hereafter is given in Table 2. The MIP formu- lation for truckload operations scheduling is given as follows: min Cb (1) subject to 「Xijk = 1 ?i ∈ L, ?j ∈ Pi (2) k ∈ Fij Sijk + Cijk ≤ MXijk ?i ∈ L, ?j ∈ Pi, ?k ∈ Fij (3) Cijk ≥ Sijk + tijk ? M(1 ? Xijk) ?i ∈ L, ?j ∈ Pi, ?k ∈ Fij (4) Sijk ≥ Ci1 j1 k ? MYiji1 j1 k ?i < i1 , ?j ∈ Pi, ?j1 ∈ Pi1 , ?k ∈ Fij ∩ Fi1 j1 (5) Si1 j1 k ≥ Cijk ? M （1 ? Yiji1 j1 k） ?i < i1 , ?j ∈ Pi, ?j1 ∈ Pi1 , ?k ∈ Fij ∩ Fi1 j1 (6)  Table 2 Notation for MIP. Indices: i loads (i, i1 ∈ L) j pallets (j, j1 ∈ P) k forklifts (k ∈ F ) Sets: L set of loads P set of pallets F set of forklifts Pi ordered set of pallets of load i (Pi ? P) Pil(i) the last pallet of Pi Fij set of alternative forklifts on which pallet Pij can be transported （Fij ? F ） Decision variables: Binary variables Xijk 1 if forklift k is selected for pallet Pij , 0 otherwise Yiji1 j1 k 1 if pallet Pij is transported (not necessarily immediately) before pallet Pi1 j1 on forklift k, 0 otherwise Continuous variables Sijk starting time of the transportation of pallet Pij on forklift k Cijk completion time of the transportation of pallet Pij on forklift k Ci completion time of load i Cb completion time of whole batch Parameters: tijk transportation time of pallet Pij on forklift k M a large number Objective function is given in (1) as minimizing the total load- ing time of the batch. Constraints (2) guarantee that each pallet is transported by only one forklift. Constraints (3) ensure that if a pallet is not assigned to a forklift, then the starting and completion time of the transportation for the pallet on that forklift is zero. If it is assigned on forklift k, constraints (4) guarantee that the completion time of the transportation for that pallet cannot be smaller than the sum of its starting time and transportation time. Constraints (5) and (6) satisfy that a forklift cannot start to carry the next pal- let until it delivers its current pallet to the corresponding forklift. Precedence constraints for each load are given in (7) which ensure that a pallet of a load cannot be carried before the transportation of the preceding pallet of the same load is ?nished. Constraints (8) and (9) give the completion time for each load and batch, respec- tively. Constraints (10)–(14) represent the binary constraints and sign restrictions for decision variables. The model given by (1)–(14) is an adjusted version of the one proposed by ?zgüven et al. [24] for FJSP. This problem can be mod- elled as a FJSP in which the loads are considered as jobs, the pallets of a load are regarded as the operations of jobs, and the forklifts used to remove the retrieving items to the trucks are seen as machines. 「 Si,j 1,k ≥ 「Ci,j,k ?i ∈ L, ?j ∈ P ? {P 1 (7) k ∈ Fi,j+1 + Ci ≥ 「Ci,P ,k k ∈ Fij ?i ∈ L (8) Cb ≥ Ci ?i ∈ L (9) Xijk ∈ {0, 11 ? i ∈ L, ?j ∈ Pi, ?k ∈ Fij (10) il(i)  k ∈ Fij i il(i) Minimization of the makespan (transportation time) is the objec- tive, as this allows minimization of the throughput time of orders and maximization of the ef?ciency of the warehouse. In FJSP, more than one operations cannot be processed on a machine at the same time. Moreover, there are technological con- straints for all jobs which satisfy the precedence relations bet