order sequencing in an automated warehouse system

2UGHU 6HTXHQFLQJ LQ DQ $XWRPDWHG :DUHKRXVH 6\VWHP

.DL *XWHQVFKZDJHU1,2 6YHQ 6SLHFNHUPDQQ1,2 DQG 6WHIDQ 9R 1

17HFKQLVFKH 8QLYHUVLWlW %UDXQVFKZHLJ ,QVWLWXW I U :LUWVFKDIWVZLVVHQVFKDIWHQ $EW -HUXVDOHP 6WUD H ' %UDXQVFKZHLJ *HUPDQ\

26LP3ODQ *HVHOOVFKDIW I U 6LPXODWLRQ EHWULHEOLFKHU $EOlXIH PE+ 6LHPHQVVWUD H ' 0 KOKHLP DP 0DLQ *HUPDQ\

$EVWUDFW

In this paper we present part of a simulation study in the field of automated warehousemanagement. The aim of the study was to provide results about the actual processing time for thedaily work load supposed to be completed in an eight hour shift. The study focussed on the ordersequencing problem having major influence on the results obtained. The problem was pidedinto two sub-problems, one being the vehicle routing problem with time windows, and tackledusing tabu search. Additionally, the integration of the model into a decision support system isproposed.

.H\ZRUGVsimulation, tabu search, warehouse systems, order sequencing problem, vehicle routing problemwith time windows

,QWURGXFWLRQThe intelligent management of warehouse systems has become a major factor with respect tocompetitiveness and customer service in a variety of industrial branches. We present a part of asimulation study in the field of warehouse management. The simulation study was carried out fora German supplier of the automotive industry. Within a more general project of restructuring thelogistic services, one specific topic was to extend the capacities of the existing warehouse at themain site of the company. The simulation model was developed using SIMPLE++, an object-oriented simulation package. Some of the features of this package are given by Levasseur [4].The automated warehouse under consideration is supposed to store about 50,000 differentarticles. The daily work load is about 8700 articles that are retrieved in containers from 25 aisles.About 10,000 containers need to be handled within the daily work shift of eight hours. Customerorders are usually known at least one day ahead and consist of different articles to be pickedfrom one to over one hundred (with an average of 4.5) locations in the warehouse. As eacharticle is stored in only one location it is most likely that not all containers belonging to an orderwill be found in one aisle. Each aisle is served by a storage and retrieval unit (SRU), that canstore up to 40 containers. All picked articles are transported on a conveyor system to theshipping area, where articles belonging to one order are brought together in special boxes.

The main emphasis of the simulation study was to provide results about the actual processingtime for the daily work load, i.e., for the time it takes to complete the entire orders of a day. Theobjective was to minimize the actual processing time, i.e. the makespan. Given that themakespan exceeds the work shift this results in respective overtimes for the employees. Theprocessing time depends on the performance of the overall system which is determined by thetime the SRUs need to retrieve the containers from the aisles and the time the employees in theshipping area need to get the commissions ready, i.e., to gather the articles of the respectiveorders and to put them in the respective boxes.

A significant and quite characteristic restriction to be considered within the shipping area is thata customer order must not be interrupted on a so-called SDFNLQJ WDEOH by another order, whichmeans that an order occupies the packing table until the last container belonging to the customerorder has been handled. If customer orders have been started by the SRUs, but no packing tablesare available the respective containers have to be stored in a buffer. Thus, the so-called orderspread, i.e., the time between the delivery of the first and the last container of a customer order inthe shipping area, has a significant impact on the utilization of the packing tables and on the totalprocessing time. As the average order-spread depends on the schedules of the SRUs theseschedules have to be determined considering both an acceptable (or scheduled) order-spread andthe retrieval times of the SRUs. Accordingly, with respect to the overall objective of minimizingthe total processing time we are facing two scheduling problems, the derivation of acceptableorder-spreads, in terms of consequences for the utilization of the packing tables, and theminimization of the SRUs retrieval times.

In the following we present a two step algorithm to compute schedules for the SRUs. We firstcalculate acceptable order-spreads and use the results for defining the restrictions of the secondproblem, a well known operations research problem, the vehicle routing problem with timewindows (VRPTW, cf. Savelsbergh [8]). This approach is promising as research has provided avariety of algorithms to provide satisfying solutions for instances of the VRPTW, and these canbe applied directly. Therefore, we focus on presenting an algorithm for tackling the firstproblem. As a result of the two algorithmic steps we obtain a schedule for the SRUs that mightbe considered as an initial solution. (Note, that this solution must not necessarily be feasible interms of definitely avoiding overtimes.)

Consequently, an algorithm to improve the initial solution has to be provided. This improvementprocedure consists of first analyzing the determined schedule by performing a simulationexperiment. Depending on the achieved order-spread in the experiment the results are then usedto either “tighten” or “loosen” certain restrictions and to tackle the concluding instance of theVRPTW anew. Additionally, a meta heuristic, which is based on the tabu search paradigm, isapplied to guide the search process.

In the sequel we describe relevant parts of the simulation model and define the schedulingproblem in m …… 此处隐藏：22786字，全部文档内容请下载后查看。喜欢就下载吧 ……