自動化外文文獻翻譯-在帶貨盤替代通道的自動化倉庫中安排整車運作【中文8400字】 【PDF+中文WORD】,中文8400字,PDF+中文WORD,自動化外文文獻翻譯-在帶貨盤替代通道的自動化倉庫中安排整車運作【中文8400字】,【PDF+中文WORD】,自動化,外文,文獻,翻譯,帶貨盤,替代,通道,倉庫,安排 Applied Soft Computing 52(2017)566574Contents lists available at ScienceDirectApplied Soft Computingj ourna l ho me page: the truckload operations in automated warehouses withalternative aisles for palletsDidem Cinara,b,Jos Antnio Oliveirac,Y.Ilker Topcua,Panos M.PardalosbaDepartment of Industrial Engineering,Faculty of Management,Istanbul Technical University,Istanbul,TurkeybDepartment of Industrial and Systems Engineering,Faculty of Engineering,University of Florida,Gainesville,United StatescALGORITMI Research Centre,University of Minho,Braga,Portugala r t i c l e i n f oArticle history:Received 5 June 2015Received in revised form 27 June 2016Accepted 13 October 2016Available online 19 October 2016Keywords:Automated storage and retrieval systemsTruckload operations schedulingFlexible job shop schedulingGenetic algorithmsa b s t r a c tIn this study,the scheduling of truck load operations in automated storage and retrieval systems isinvestigated.The problem is an extension of previous ones such that a pallet can be retrieved from a set ofalternative aisles.It is modelled as a flexible job shop scheduling problem where the loads are consideredas jobs,the pallets of a load are regarded as the operations,and the forklifts used to remove the retrievingitems to the trucks are seen as machines.Minimization of maximum loading time is used as the objectiveto minimize the throughput time of orders and maximize the efficiency of the warehouse.A prioritybased genetic algorithm is presented to sequence the retrieving pallets.Permutation coding is usedfor encoding and a constructive algorithm generating active schedules for flexible job shop schedulingproblem is applied for decoding.The proposed methodology is applied to a real problem arising in awarehouse installed by a leading supplier of automated materials handling and storage systems.2016 Elsevier B.V.All rights reserved.1.IntroductionAutomated storage and retrieval system(AS/RS)is a warehous-ing system that uses mechanic devices for the storage and retrievalof products in both distribution and production environments 1,2.Automatic cranes move through aisles between racks to put theitems on the racks and retrieve those items from storage to the col-lector for fulfilling the customer orders.AS/RS is fully automated,because no intervention of an operator is needed for handling thepallets 2.When an order is received for an item,a stacker craneretrieves 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 theend of the roller conveyor,the conveyed pallet is picked up usinga forklift truck.High space utilization,improved material flow,andimproved inventory control are some of the advantages of AS/RS 3.The best utilization from such a system can be succeed by optimaldesign and optimal scheduling of the system.Warehouse scheduling optimization is a combinatorial opti-mization problem which cannot be solved with exact algorithmsin 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:cinarditu.edu.tr(D.Cinar),zandps.uminho.pt(J.A.Oliveira),topcuilitu.edu.tr(Y.Ilker Topcu),pardalosufl.edu(P.M.Pardalos).Because of the high complexity of the problem,simulation andmetaheuristics have been widely used in warehouse schedulingoptimization 4.A detailed literature review about the method-ologies developed for AS/RS design and scheduling is given inSection 3.In this study,the scheduling of truck load operations arisingin AS/RS is investigated.The problem is modelled as a flexible jobshop scheduling problem(FJSP)by considering the loads as jobs andpallets of a load as its operations.The forklifts which are used fortransportation of pallets from collectors to trucks are consideredas machines.The main contributions of this paper are twofold:(1)scheduling of truck load operations is modelled as a flexible jobshop scheduling problem,(2)a real problem arising in an AS/RSwarehouse installed by a leading supplier of automated materialshandling and storage systems is solved by using a priority basedgenetic algorithm and the effect of aisle selection flexibility is inves-tigated.To the best of the authors knowledge,this work is thefirst time that the FSJP is used to model the retrieving operationof pallets in an AS/RS warehouse.The paper is organized as follows.Section 2 provides a briefexplanation on investigated automated storage system.In Sec-tion 3,a literature review on scheduling of truck load operationsis given.Section 4 represents a mixed integer programming(MIP)formulation for a truckload operations scheduling problem in AS/RSand discusses the modelling of the problem as a flexible job shopscheduling problem.Section 5 presents the devoted methodology.http:/dx.doi.org/10.1016/j.asoc.2016.10.0131568-4946/2016 Elsevier B.V.All rights reserved.D.Cinar et al./Applied Soft Computing 52(2017)566574 567Fig.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 systemThe methodology proposed in this study is applied to an AS/RSwarehouse in Italy which works as a distribution center.Productsare stored by the warehouse and loaded to the trucks to fulfillthe orders of customers.Routes of the trucks,which are known inadvance,are determined considering the delivery deadline of cus-tomer orders.The warehouse consists of eleven aisles constitutedby pallet racks with the capacity of 40,000 pallets.An automaticstacker crane or S/R machine works in each aisle to move the palletsfrom their respective rack to the collector at the beginning of theaisle.Forklifts transport the pallets to the trucks.The warehousehas 13 docking bays to load the trucks.A scheme of the loadingprocess in this warehouse is shown in Fig.1.Warehouse Planning System(WPS)and Warehouse Manage-ment System(WMS)are used to operate the warehouse.Dailyplanning of loadings for each truck is executed by WPS.Thesequence of retrieving pallets and the movement of S/R machinesand forklifts are determined by WMS.Approximately one hun-dred loads are retrieved per day by a truck.Each truck has its owndelivery time which is considered by WPS and loading must notbe delayed.In the strategy defined for the WPS,the whole set ofloads are divided into subsets called batches.Loads in a batch areprocessed simultaneously.Loading of a batch cannot be startedbefore the loads of previous batch are finished.The size of a batchis determined with respect to delivery deadlines and the numberof docking bays.A standard daily plan includes 1520 batches with613 loads for each one.An order of a customer consists a product or a set of products thatare delivered on one or more pallets.The set of products for an orderis known in advance,and it is available in the warehouse.A truckload consists of a set of pallets transported for one or more clients.The sequence of loading pallets on the truck is determined by WMSwith LIFO(Last In First Out)rule.Since the sequence of pallets in aload is predetermined and cannot be changed,precedence relationsexist between pallets of a load.The pallets of a load can be retrieved from any aisle.To facilitatethe assignment of the trucks to the docking bays,several palletsare placed in different aisles to reduce the time of load prepara-tion,allowing a pallet to be selected in an aisle that is close tothe truck and respecting the FEFO(First-Expired-First-Out)rule.The S/R machine is programmed to retrieve the pallets from thecorresponding aisle.We assume that each forklift can work for only one aisle.Aftera forklift receives a pallet from its own aisle,it can carry the palletto any truck.For safety reasons,more than one forklift cannot beallowed to place pallets in a truck at the same time.So,one loadshould receive one pallet at a certain time.After a pallet is loadedto the truck,the forklift returns to its aisle and communicates toWMS that it is available for a new transportation.Then the nextpallet for the same load is programmed.A forklift can receive onlyone pallet at each transportation.Detailed information about theanalysed AS/RS warehouse can be obtained from 5.Different sequences of pallets in a batch retrieved by S/Rmachines result in different processing times.An illustrative exam-ple is the following.Assume that there are 5 aisles in the warehouserepresented by A1,A2,.,A5.The problem is planning the retriev-ing sequence of a batch including 3 loads.Each load consists of 4pallets,which have precedence relations in advance,representinga total of 12 pallets to be retrieved in the batch.There is one forkliftfor each aisle to carry the pallets from the aisle to the correspond-ing truck.Although a pallet can be retrieved from several aisles,inprevious studies 5,6 it was assumed that it is the WMS that previ-ously selects the pallets considering the distance to the aisle wherethe load is prepared.The aisle for each pallet and the processingtimes are given in Table 1.The aisle storing pallet j and the transportation time betweenrelated aisle and truck are shown as(Ak,t)where Akrefers thekth aisle and t is the transportation time from aisle Akto truck.For example,the first pallet of the second load must be retrievedTable 1An illustrative example for real problem.jth palletLoad i 1 2 3 41(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)566574Fig.2.Two different schedules for retrieving the pallets.from the third aisle with time 1.For convenience,the pallets wereconsecutively numbered from 1 to 12.Fig.2 shows two different sequences of retrieving pallets.The numbers inside the rectangles identify the pallets.For eachsequence,Fig.2 presents the Gantt chart for the set of aisles(leftside)and the Gantt chart for the set of loads(right side),whichrepresents better the processing time of the batch.The sequencesfor retrieving pallets only differ at Aisle 3,where the pallet 11 iscollected either after pallets 3 and 7(Fig.2(a),or before pallets 3and 7(Fig.2(b).The decision when to retrieve pallet 11 producessignificantly different processing times for the entire batch of loads.Fig.2(a)presents the optimal solution for this small example.3.Literature reviewIn an AS/RS,planning and performing of accurate loading pro-cesses are very important to meet the customer orders at theproper time 5.Among previous studies,analysis oriented onesconstituted the majority of the literature rather than those devel-oping models and techniques for warehouse design 7.Simpleheuristics and simulation techniques were used for storage andretrieval problems in automated warehousing systems.Bozer andWhite 8 proposed travel time models for automated S/R machineswith single and dual command mode.Han et al.9 proposed anearest neighbour heuristic for retrieval sequencing in AS/RS withdual command cycles and used Monte Carlo simulation for eval-uation.Eben-Chaime 10 also used a nearest neighbour heuristicto sequence the retrievals.Hausman et al.3 compared severalstorage assignment rules to determine the optimal storage assign-ment policy.Schwarz et al.11 analysed both storage assignmentand interleaving rules with a simulation model.Lee and Schae-fer 12 formulated the problem,which is also handled by Hanet al.9,as an assignment problem.They proposed a methodologycombining the Hungarian method and the ranking algorithm forthe assignment problem with the tour-checking and tour-breakingalgorithms.In the last few years,besides the mathematical modeling andsimulation approaches,metaheuristics have been used in theseareas.Comprehensive reviews of warehouse design and control canbe found in de Koster et al.13,Gu et al.14 and Baker and Canessa15.Moreover,detailed explanations of the current state of theart in AS/RS design are provided by Roodbergen and Vis 2 andVasili et al.16.Manzini et al.17 developed a multi-parametricdynamic model for a product-to-picker storage system with class-based storage allocation of products.They investigated the factorsaffecting the warehousing system performance.Yin and Rau 18combined simulation and genetic algorithms for the dynamic selec-tion of sequencing rules for a class-based unit-load AS/RS.Changet al.19 proposed a multi-objective mathematical programmingmodel and a genetic algorithm for the order picking of stackercranes.Kung et al.20 developed a dynamic programming basedorder scheduling methodology for the AS/RS with multiple stackercranes on a common rail.The problem includes both assignmentof orders to each crane and scheduling of cranes without collision.Brezovnik et al.21 used a multi-objective ant colony optimizationmethod for the storage allocation problem in an AS/RS.Based onthe computational results obtained from a home appliance deviceswarehouse,it was shown that optimal space utilization can beachieved when the products with lower weight and height arestored at higher levels.Yang et al.22 inferred that the speed profileof an S/R machine has an important effect on the optimal stor-age rack for a multi-deep AS/RS.Atmaca and Ozturk 4 proposeda mathematical programming model and a simulated annealingapproach for the storage allocation and storage assignment prob-lems to minimize storage costs.Optimal solution was obtained bythe proposed mathematical model for problems having up to 103materials.Dooly and Lee 23 modelled a shift-based sequencingproblem 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 loadoperations on an AS/RS warehouse as a job shop scheduling prob-lem(JSP)with recirculation 5.Oliveira 5 assumed identicalprocessing times to transport pallets independently of the locationD.Cinar et al./Applied Soft Computing 52(2017)566574 569of the aisle and the truck.Figueiredo et al.6 extended the problemby considering different processing times and solved it by geneticalgorithms with random keys representation.Both Oliveira 5 andFigueiredo et al.6 assumed that a pallet can be retrieved from oneaisle previously decided by WMS,considering the proximity to thedocking bay.In this study,this assumption is extended by consid-ering alternative aisles for pallets.The selection of the aisle wherethe pallets are retrieved is determined with truck load schedulingsimultaneously.So the problem consists of both selection of an aisleto retrieve the pallet,which is currently performed by WMS,andthe scheduling of pallets transportation from collector to truck.Inthis way,the benefit of combining these two operations is inves-tigated.No study which addresses this problem as a FJSP has beenencountered in the scope of this study.4.Modelling AS/RS warehouses as FJSPIn this section,a MIP formulation for the truckload operationscheduling problem is presented.We do not consider cross-dockingor order picking to produce a pallet.The assumptions consideredin this study are given as follows:an order is formed by only(complete)pallets of products that arestored in the warehouse.an S/R machine is faster to put a pallet on the collector than aforklift to remove a pallet and an S/R machine operates in advanceof the forklift,a collector works as a buffer with capacity for several pallets,the flow of pallets in the collector(gravity roller conveyor)followsthe FIFO rule,an S/R machine takes zero units of time to put a pallet in thecollector.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?k FijXijk=1 i L,j Pi(2)Sijk+Cijk MXijki L,j Pi,k Fij(3)Cijk Sijk+tijk M(1 Xijk)i L,j Pi,k Fij(4)Sijk Ci?j?k MYiji?j?ki i?,j Pi,j?Pi?,k Fij Fi?j?(5)Si?j?k Cijk M?1 Yiji?j?k?i i?,j Pi,j?Pi?,k Fij Fi?j?(6)?k Fi,j+1Si,j+1,k?k FijCi,j,ki L,j Pi?Pil(i)?(7)Ci?k FijCi,Pil(i),ki L(8)Cb Cii L(9)Xijk?0,1?i L,j Pi,k Fij(10)Yiji?j?k?0,1?i i?,j Pi,j?Pi?,k Fij Fi?j?(11)Sijk,Cijk 0 i L,j Pi,k Fij(12)Ci 0 i J(13)Cb 0(14)Table 2Notation for MIP.Indices:i loads(i,i?L)j pallets(j,j?P)k forklifts(k F)Sets:L set of loadsP set of palletsF set of forkliftsPiordered set of pallets of load i(Pi P)Pil(i)the last pallet of PiFijset of alternative forklifts on which pallet Pijcan be transported?Fij F?Decision variables:Binary variablesXijk1 if forklift k is selected for pallet Pij,0 otherwiseYiji?j?k1 if pallet Pijis transported(not necessarilyimmediately)before pallet Pi?j?on forklift k,0 otherwiseContinuous variablesSijkstarting time of the transportation of pallet Pijon forklift kCijkcompletion time of the transportation of palletPijon forklift kCicompletion time of load iCbcompletion time of whole batchParameters:tijktransportation time of pallet Pijon forklift kM a large numberObjective function is given in(1)as minimizing the total load-ing time of the batch.Constraints(2)guarantee that each palletis transported by only one forklift.Constraints(3)ensure that if apallet is not assigned to a forklift,then the starting and completiontime of the transportation for the pallet on that forklift is zero.If it isassigned on forklift k,constraints(4)guarantee that the completiontime of the transportation for that pallet cannot be smaller thanthe 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 ensurethat a pallet of a load cannot be carried before the transportationof the preceding pallet of the same load is finished.Constraints(8)and(9)give the completion time for each load and batch,respec-tively.Constraints(10)(14)represent the binary constraints andsign restrictions for decision variables.The model given by(1)(14)is an adjusted version of the oneproposed by zgven et al.24 for FJSP.This problem can be mod-elled as a FJSP in which the loads are considered as jobs,the palletsof a load are regarded as the operations of jobs,and the forklifts usedto remove the retrieving items to the trucks are seen as machines.Minimization of the makespan(transportation time)is the objec-tive,as this allows minimization of the throughput time of ordersand maximization of the efficiency of the warehouse.In FJSP,more than one operations cannot be processed on amachine at the same time.Moreover,there are technological con-straints for all jobs which satisfy the precedence relations betweenpallets.In the warehouse,forklifts can carry only one pallet at a cer-tain time like the machines in FJSP.Similarly,there is a receivingorder of pallets for each load that should be guaranteed.No palletcan be loaded before the former one.In other words,overlappingthe transportation of pallets of the same load is not allowed.Theorder of pallets of each load can be taken into account as techno-logical constraints.In the warehouse,loads can be realized simultaneously andshould be ended inside the time window determined by WPS.All570 D.Cinar et al./Applied Soft Computing 52(2017)566574Table 3An example for real problem.jth palletLoad i 1 2 3 41(A1,1),(A3,3)(A2,2),(A5,5)(A3,3)(A4,4),(A5,5)2(A2,2),(A3,1)(A1,3),(A5,3)(A2,2),(A3,1)(A1,3),(A4,2)3(A4,2)(A2,4),(A4,2)(A1,5),(A3,3)(A5,1)loads should be concluded as soon as possible to facilitate loadingthe following batch.Preparation of a new batch cannot be starteduntil all loads of the current batch are loaded.Terminating the load-ing of batches sooner and reducing the occupation of docks areachieved by minimization of makespan.The following illustrative example is an extension of the exam-ple represented before.Some pallets can now be retrieved fromtwo aisles,the previous one and a new alternative which has agreater processing time.The alternative aisles for each pallet andthe processing times are given at T