ARTICLE IN PRESS Control Engineering Practice 13 (2005) 1223–1241 www.elsevier.com/locate/conengprac An approach to control automated warehouse systems Francesco Amatoa, Francesco Basileb,, Ciro Carboneb, Pasquale Chiacchiob a School of Computer Science and Biomedical Engineering, Università degli Studi Magna Græcia di Catanzaro, Via Tommaso Campanella 115, 88100 Catanzaro, Italy b Dipartimento di Ingegneria dell’Informazione ed Ingegneria Elettrica, Università degli Studi di Salerno, Via Ponte Don Melillo 1, 84084, Fisciano (SA), Italy Received 18 March 2003; accepted 28 October 2004 Available online 29 January 2005 Abstract The goal of this paper is the development of control algorithms for the management of an automated warehouse system. As usual, the implementation of a control algorithm requires three preliminary steps: development of a reliable model; design of control procedures according to some optimality criteria; validation of these control procedures. As for modelling, a new level in the control architecture, namely an optimizer system, is introduced which performs real-time optimization thus simplifying the low-level control and improving the overall performance. In this context, the role of a detailed model of the whole warehouse is discussed and such a model is built up by using the colored timed Petri nets framework. As for control, we propose two control algorithms, derived under the simplifying continuity assumption of the rack locations, to optimize the operations of the cranes (moving within the aisles of the warehouse) and the operations of the shuttle (moving on a straight line placed between the aisles and the picking/refilling area), respectively. To evaluate the performance of the proposed control algorithms we define three different cost indices. As for the validation, extensive simulations are performed on the model in order to prove the effectiveness of the proposed control algorithms. A further validation of the algorithms has been performed on a test bed in order to take into account communication delays and computation times. Finally, the proposed architecture and control algorithms have been applied to a real plant. r 2004 Elsevier Ltd. All rights reserved. Keywords: Discrete event systems modelling; Colored timed Petri nets; Warehouse automation; Factory automation; Optimization 1. Introduction In the last fifteen years, a big effort has been made to find optimal strategies for planning and control of warehouse systems. These issues have become more and more challenging with the growth and diffusion of modern computer technology which allows the implementation of complex operations in a completely automatic way. Planning involves high level decisions, like assignment of goods to the storage locations (random, class-based, correlated product clustering policies) (VandenBerg, 1999) or the designing of the Corresponding author. Tel.: +39 089 964400; fax: +39 06 233227957. E-mail addresses: fbasile@unisa.it, balraj@macmill.com (F. Basile). 0967-0661/$ - see front matter r 2004 Elsevier Ltd. All rights reserved. doi:10.1016/j.conengprac.2004.10.017 warehouse system itself. Control problems involve optimal sequencing and scheduling of storage and retrieval requests resulting in the so-called dispatching control. We refer to a general warehouse architecture consisting of a number of aisles, each one served by a crane, shuttles, picking/refilling positions and in/out buffers (see Fig. 1 for an example of a real layout). On both sides of each aisle there is a storage rack composed of nr rows and nc columns; moreover, as said, each aisle is served by a crane, capable of moving both vertically and horizontally at the same time, which performs the following operations: (i) picking of the Stock Unit (SU) to be stored at the buffer input of the aisle, referred as the input/output (I/O) point of the aisle; (ii) storage of the SU into the assigned location S ARTICLE IN PRESS 1224 F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 Fig. 1. Warehouse lay-out. of the rack; (iii) movement to location R where a retrieval has been requested; (iv) retrieval of the SU stored in R; (v) coming back to the I/O point. This set of operations is called, in the warehousing system context, a dual command (DC) machine cycle (Graves, Hausman, & Shieh, 1977; Bozer & White, 1984; Han, McGinnis, Shieh, & White, 1987; Lee, de Souza, & Ong, 1996). As to the shuttle, it moves along a mono-dimensional path placed orthogonally with respect to the aisle axis and performs picking actions (from the main input buffer, the aisles output locations and the picking/ refilling output locations) and deposit actions (into the main output buffer, the aisles input locations, the picking/refilling input locations). The picking–refilling areas represent an interface with the shop floor of the factory. A picking–refilling bay (denoted as ‘‘BayPR’’ in Fig. 1) consists of a picking location, a deposit location and a shop floor interface location connected via conveyors so that an SU (carried on a pallet) can be partially emptied by a human operator at the shop floor location and then carried back on the same pallet to an aisle rack location. The in/out buffers represent the interface of the warehouse with the rest of the plant. In this paper an approach to the control of warehouse systems is presented. The first contribution of this paper is the development of a new hierarchical level in the control architecture (Basile, Carbone, & Chiacchio, 2003). Indeed, in previous applications, only long-term optimization was performed: it usually has a day or week time horizon and it is based on simplified models of warehouse systems and on statistical characterization of the system performance. Conversely, we introduce a further level constituted by a real time optimizer, whose core is the dispatcher unit, with the aim of performing the shortterm optimization of handling sequences, that usually has the objective to minimize the time to complete a little number of picking or storage missions and is based on the current state of the system. The role of a detailed model for the designing and implementation of this level is also discussed. The main advantages obtained are:



The short-term optimization leads to better performance. Design, implementation and testing of low-level handling sequences is greatly simplified since all the optimization issues are taken in charge by the dispatcher. Since the optimizer relies on the current state of the system (it works in real time) it can also manage faults and degradation of the system. Roughly speaking, the dispatcher output is the order to start handling sequences whose control code is executed at low-level; therefore, it can be easily adapted to different plants. The second contribution of this paper is the development of a detailed formal reliable model of an automated warehouse, as shown in Fig. 1, in the framework of discrete event systems; model building is fundamental for both control design and performance evaluation. The obtained model is based on the colored timed Petri net ARTICLE IN PRESS F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 (CTPN) approach (Jensen, 1995; Hsieh, HWang, & Chou, 1998). In this context the key contributions of the paper can be summarized as follows:




A detailed formal model of the whole warehouse is built up, while the previous literature mainly considered the formal modelling of the individual components (Hsieh, HWang, & Chou, 1998) or only implemented a simplified model for simulation purposes (Lee et al., 1996; Chincholkar & Krishnaiah Chetty, 1996). The model is highly modular and each module is parameterized: the reuse of model components to model different warehouse systems is very easy. The interface with a higher level scheduler (dispatcher) is embodied in the obtained model, thus allowing off-line performance evaluation of state-dependent dispatching control algorithms. There is a clear correspondence between model entities and layout, thus allowing the model to be used for on-line monitoring (see (Feldmann & Colombo, 1999) for monitoring of flexible manufacturing systems). The detailed model can be used on-line in complex control algorithms which are based on look-ahead (or what-if) techniques (Hsieh & Chen, 1999). The third contribution is the development of the control algorithms implemented in the optimizer system (OS). More precisely we focus on simultaneous optimization of the DC cycles operations of the cranes and the picking/deposit actions performed by the shuttle. Previous papers (Bozer & White, 1984) and (Han, McGinnis, Shieh, & White, 1987) considered the DC optimization problem under the continuous rack assumption, i.e. the rack is viewed as an infinite number of pointwise locations each one addressed by a pair of real numbers. In (Han, McGinnis, Shieh, & White, 1987) the nearestneighbor algorithm to optimize the sequence of retrievals was proposed. This algorithm assumes that, for any given DC operation, a number of locations is available for storage and one of the empty locations is paired with a retrieval location in an optimal way. The throughput derived by the application of such policy is evaluated analytically by an approximated formula, and then validated via computer simulations on both continuous and discrete racks. In the same context of Bozer and White (1984) and Han, McGinnis, Shieh, and White (1987), Lee and Schaefer (1996) proposed a procedure to optimize the sequencing of retrieval requests based on the solution of a linear assignment problem. By following the guidelines of Bozer and White (1984), Han, McGinnis, Shieh, and White (1987) and Lee and Schaefer (1996), in this paper we develop an algorithm to optimally sequence the retrieval orders. 1225 However, we start from the more restrictive assumption (which is based on real world experience) that the SU to be stored arrives at the I/O point with the address of the destination location already assigned. This means that it is not possible, at this level, to choose the destination among a number of empty locations, as assumed in previous papers. Moreover we propose a procedure, based on parametric identification techniques, to compute precisely the throughput of the crane/aisle subsystem which comes out from the application of our algorithm. The continuous approximation allows us to express the throughput improvement as a function of a small number of meaningful parameters. The problem of shuttle optimization in warehouse system of the type in Fig. 1 has not been previously discussed in the literature. We propose an algorithm to optimize the sequence of picking and deposit operations performed by the shuttle, so as to minimize the time required by each cycle. Assuming again a continuous structure for the locations placed along the shuttle path, we evaluate the theoretical improvement of the shuttle sub-system throughput obtained by the application of the proposed algorithm, with respect to the case in which no optimization is considered. A key point in the development of our optimization is that, as we shall show, the cranes optimization is independent (in a sense to be specified) from the shuttle optimization and therefore they can be performed separately. The CTPN model of the warehouse is used for the performance evaluation of the control algorithms. 2. Automated warehouse control: the role of the optimizer system The main task of a warehouse system is to store and retrieve goods. We refer to the goods in terms of SUs, which are the entities the system can handle. In most part of the systems operating today the automated warehouse management is carried out by a control system which consists of three different levels:


PS (Planning System—Level 3), MS (Management System—Level 2), HS (Handling System—Level 1). In this context, the MS receives the loading/unloading planning from the PS and based also on the location map (i.e. the list of the SUs stored in the warehouse and the coordinates of their location), provides to the HS a set of complex handling requests, hereafter named missions, to be executed. It also communicates to the PS the inventory items. The role of PS can be resumed as follows: PS does not know where an SU is, but it only knows whether an SU ARTICLE IN PRESS 1226 F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 is or is not in the warehouse, thus it can order to pick it by sending a retrieval mission to MS; PS does not know where an SU has to be stored but it only knows that there is at least an empty location in the warehouse, thus it can send a storage mission to MS. PS works on a statistical characterization of the system performance. Its main task is material planning and lot-sizing keeping in mind the constraints concerning the inventory levels, buffer capacities and production times. The MS at level 2 knows only the warehouse location map, but not the actual state of the whole plant (crane and shuttle positions, tracking position state). Therefore, level 2 schedules the missions to be performed exclusively on the basis of the state of the warehouse location map by using its optimal management algorithm. The HS is dedicated to the control and coordination of the plant devices (conveyors, buffers, cranes, shuttle, etc.). As said, it receives by the MS the set of missions, which must be executed by controlling and coordinating different devices. For instance, a mission could request to move an SU from the main input buffer to a specific location in one of the aisles. Moreover, the HS has to manage multiple missions at the same time. Finally it communicates to the MS the result of the missions. A number of physical locations where an SU can stand and be detected are distributed within the plant. A logical record corresponds to each location where the data concerning the SUs and their state (present/absent) are stored; these locations are called tracking positions. The HS task is to manage the shifting of tracking data according to the real SU movements in the plant. To this end the HS knows all plant information (actual location of cranes and shuttles, the state of SUs, etc.). On the other hand, performing real-time optimization at this level presents some disadvantages, as it is discussed afterwards. On the basis of the above considerations, we propose to separate the handling phase from the optimization phase by introducing another intermediate level, the OS, between the MS and the HS (Fig. 2). This reflects the recent trend to bridge the gap between the planning/ management system and the control system of a factory using on-line information to manage the current application of manufacturing resources; more in general this level is referred in technical literature as Manufacturing Execution System. In our approach, the SU movements in an automated warehouse are carried out by subdividing the given mission into several basic handling sequences. In this context, the HS is used for the sole basic handling sequences (for example crane_goes_to_position_X, shuttle_picks_SU_from_buffer, etc.) while the OS takes charge of the real-time optimization based on the current state of the plant. Therefore, the OS receives the list of missions from level 2 MS, Fig. 2. Optimization module in the software architecture. reschedules and segments them into basic sequences according to the plant state and the appropriate optimization policy; such sequences are then communicated to the HS to be executed. To perform the movement, simple functions which implement those basic sequences are needed. The expected advantages are:





The development of the HS code is greatly simplified. Testing and debugging of the HS is simplified and can also be performed if other levels have not been developed yet, thus reducing the start-up time for the plant. The basic sequences are similar for different warehouse systems; therefore code reusability is easily achieved. The OS can be developed and tested via computer simulation if a detailed model of the plant, as controlled by the HS, is available. Currently the HS is implemented on a programmable logic controller which does not always allow the coding of complex algorithms. Since, by our approach, the OS can be physically separated from the HS, it is possible to implement the OS on a different machine. As will be presented later, the interface between the OS and the HS is very simple, thus making software portability easier. 3. Model requirements The modelling of a warehouse system can be performed at various levels of complexity. The level of ARTICLE IN PRESS F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 modelling can range from very aggregate to very detailed, according to the user’s requirements for system analysis and control. In this paper, a detailed modelling approach is presented. The proposed model can be used at different steps of the automated warehouse system design. In the initial phase of warehouse sizing the availability of a detailed model allows the evaluation of the storage area sizes. At this level the user needs to determine the number of shuttles and cranes required to handle the expected amount of materials. This is often an important design issue due to costs and lead times for special vehicles. The user may also wish to model the interactions of the warehouse with other areas of the factory in order to see how these interactions affect the overall system performance. During the test phase the logic of the warehouse control system has to be verified. The purpose is to check if all the movements of the warehouse components are executed according to the specifications and that no deadlock occurs. Moreover, in the presence of decisions based on priorities, it is very important to evaluate the validity of the control algorithm, in order to observe how mission dispatching affects the system performance. In this paper we refer to the automated warehouse architecture shown in Fig. 1. The main problems encountered in warehouse system modelling are listed below. Resource attributes: SUs are identical in their functionality. However the state attributes (e.g. loaded, empty), the destination of the load (coordinates of the rack location), the kind of operation to be performed (storage operation, retrieval operation) make them different from each other. Higher-level scheduler integration: It is important to remark that the model must represent the plant ‘‘as controlled by the HS’’. This means that the communication interface between the HS and the OS must be included in the model. Operation time: The model must include timing information. For instance, all loading/unloading activities of cranes take time; moreover, the time required to pick-up a pallet depends on the distance between the current position of the crane and the rack location where it is stored. Modular design: During the system life-cycle, it may happen that a component (e.g. a shuttle, a crane, etc.) is added or removed; moreover, it is important to achieve the component re-use. Therefore, it is convenient to divide the warehouse model into sub-models and define a standard interface for the communication between them; also, this approach may reduce the simulation complexity. We use colored timed Petri nets for the model since they allow us to fulfill all the above requirements. 1227 4. The model For the sake of brevity, we present in detail only the obtained sub-model of the cranes. See (Basile, Carbone, & Chiacchio, 2001) for more details about the whole model. Indeed this sub-system is present in almost all warehouse systems and therefore it is of general interest. Moreover, most of the complexity in modelling a warehouse system relies on the above sub-systems. Indeed the input and output buffers, their size, number and placement are strictly dependent on the particular warehouse; in addition, they do not present any conceptual difficulty in the modelling phase. The CTPN model of the generic crane sub-system, called CRANEi ; and of the interface between a generic crane and the shuttle sub-systems (with two bays) are shown in Figs. 3 and 4, respectively. In Tables 1 and 2 the interpretation of all transitions and places of the crane CTPN model is described. The sub-system models are all parameterized. For instance, the CRANEi net model is parameterized with respect to the size of aisle input/output buffers (index p in Fig. 3 and Table 2). Other parameters are related to the operation timing. After recalling some technical details concerning PN modelling (DiCesare, Harhalakis, Proth, Silva, & Vernadat, 1993; Murata, 1989; Silva & Teruel, 1997; Ramaswamy & Valavanis, 1994), we show how the four problems described in the previous section are solved for each sub-system of the warehouse. 4.1. Background CTPNs extend the framework of PNs by adding color, time and modular attributes to the net. The color attribute is developed to deal with systems that have similar or redundant logical structures. The time attribute allows various time-based performance measures to be added in the system model. We assume that the reader already knows CPN concepts and terminology as introduced in Jensen (1995). Let us recall here the main characteristics of CPNs we deal with in this work. A multi-set m is a set which may contain multiple occurrences of elements of a non-empty set S. Formally, a multi-set is a function m : S ! N; where N is the set of non-negative integers, which we represent as a formal sum X mðsÞs: s2S We denote by: S MS the set of all multi-sets over S; TypeðvÞ the type of a variable v; TypeðexprÞ the type of an expression expr; VarðexprÞ the set of variables in an expression expr. In addition we define the binding of a ARTICLE IN PRESS 1228 F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 Fig. 3. CRANEi CTPN module. set of variables V as the function b associating to each variable v 2 V an element bðvÞ 2 TypeðvÞ and exprhbi as the value obtained by evaluating an expression expr in a binding b, i.e. substituting for each variable v 2 VarðexprÞ the value bðvÞ 2 TypeðvÞ determined by the binding. Now we recall the following definition (Jensen, 1995). Definition 1. A CPN is ðS; P; T; A; N; C; G; E; IÞ where a 9-tuple CPN ¼ S is a set of non-empty types, called color sets; P is a finite set of places drawn by circles; T is a finite set of transitions including immediate transitions drawn by black bars and timed transitions drawn by empty boxes; A is a finite set of arcs such that P \ T ¼ P \ A ¼ T \ A ¼ ;; N is a node function defined from A to P T [ T P; C is a color function defined from P into S; G is a guard function defined from T into expressions such that 8t 2 T : ½TypeðGðtÞÞ is boolean ^TypeðVarðGðtÞÞÞ  S; E is an arc expression function defined from A into expressions such that 8a 2 A : ½TypeðEðaÞÞ ¼ CðpÞMS ^ TypeðVarðEðaÞÞÞ  S; where p is a place of NðaÞ; I is an initialization function defined from P into closed expressions such that 8p 2 P : ½TypeðIðpÞÞ ¼ CðpÞMS : In order to define the binding of a transition t we introduce the following notation: ARðtÞ ¼ fa 2 AjNðaÞ 2 P ftg [ ftg Pg; VarðtÞ ¼ fvjv 2 VarðGðtÞÞ _ 9a 2 ARðtÞ : v 2 VarðEðaÞÞg: A binding of a transition t is a function b defined on VarðtÞ such that v 2 VarðtÞ : bðvÞ 2 TypeðvÞ and GðtÞhbi ¼ 1; ARTICLE IN PRESS F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 1229 changes according to M 2 ðpÞ ¼ M 1 ðpÞ  X Eðp; tÞhbi ðt;bÞ2Y þ X Eðt; pÞhbi 8p 2 P: ðt;bÞ2Y In this case we say that M 2 is reachable by M 1 : This is written as M 1 ½Y 4M 2 : The introduction of a timing specification is essential in order to use Petri net models for performance evaluation of distributed systems. We consider nets with deterministic timing and one phase firing rule, i.e. a timed enabling (called the service time of the transition) followed by an atomic firing. Service times of transitions are supposed to be mutually independent and time independent. A time function f : BðtÞ ! R is introduced; it is the time required by the timed transition t associated with a binding b to complete the firing. After time function has been introduced, we speak of CTPN models. In a colored Petri net model two kinds of conflicts may arise: conflicts among transitions and conflicts among bindings. In this paper the following solution has been adopted:
Fig. 4. Interface between shuttle and Cranei CTPN modules. i.e. the guard function is true. BðtÞ denotes the set of all bindings for t. A token is a pair ðp; cÞ where p 2 P and c 2 CðpÞ; while a binding element is a pair ðt; bÞ where t 2 T and b 2 BðtÞ: The set of all token elements is denoted by TE while the set of all binding elements is denoted by BE. A marking is a multi-set over TE while a step is a non-empty and finite multi-set over BE. The sets of all markings and steps are denoted by M and Y, respectively. We assume S ¼ S1 S 2    S n and that a function between each set S i and the integer number set Z is defined; this leads us to represent a token in a place p by a n-tuple hti ¼ ðc1 ; c2 ; . . . ; cn Þ; where cj is an integer. We represent by ð1Þ the black token, i.e. the token having no color. A step Y is enabled in a marking M iff the following property is satisfied: X 8p 2 P : Eðp; tÞhbipMðpÞ: ðt;bÞ2Y When a step is enabled in a marking M 1 it can occur and, if the transition t fires in binding b, the net marking
In order to avoid the coupling between resolution of conflicts1 and duration of activities,2 transitions in conflict are supposed to be immediate except for timed transitions modelling a watchdog timer or immediate transitions modelling a failure detection; only in these special cases it is allowed that a timed transition, modelling a watchdog timer, can interrupt another timed transition or that an immediate transition, modelling an error detection, can be in conflict with a timed transition. In general, in a PN model there is no need of removing tokens from a place in the same order as they were added. However, in our case, when the tokens contained in a place represent SUs, it is important to preserve the incoming order for their removing. Therefore, we assume each place as being a queuing place with a FIFO policy. Thus, no conflict among bindings may arise. We denote a net place by Pfx; yg; where x denotes the sub-system of the model and y denotes the index of the place inside the sub-model; we assume that, in general, a number of nt aisles is present and therefore nt þ 1 1 We say that two or more transitions are in conflict if they have common input places. 2 When a timed activity is associated with transitions, a conflict resolution policy may be a race between conflicting transitions, that has no sense in presence of a physical plant. ARTICLE IN PRESS F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 1230 denotes the shuttle sub-system net model. Fusion places, source places and sink places (see Sections 4.3 and 4.5) are denoted by Pf fxg; Psrfxg; Pskfxg; respectively, and are all drawn by double circles. The following expression functions, used in the arc expressions and guard functions, are defined: (i) prðp; c1 ; c2 ; . . . ; ck Þ: for each token hti in the place p the function builds a new token formed only by the specified components c1 ; c2 ; . . . ; ck of the token hti; (ii) concðht1 i; ht2 i; . . . ; htk iÞ: the function builds the new token ðht1 i; ht2 i; . . . ; htk iÞ formed by the concatenation of the specified components; (iii) id: this function selects all the components of a token. 4.2. Resource attributes The use of a CPN allows us to completely solve the problem of the resource attribute representation, since the token color univocally identifies a pallet or the state of a device. For example, in the crane model (see Fig. 3), place Pf f2ig has format ðsh; bay; IDSU ; comÞ: Thus, the presence of a token in this place means that a shuttle is aligned to the input buffer of the crane with pallet IDSU on bay bay; moreover, command com (explained later) has to be performed on pallet IDSU. Without using CPN formalism we would need a different place for each identification number of the pallet and for each bay of the shuttle. 4.3. Higher level scheduler integration The modelling of the communication between the OS and the sub-systems as controlled by the HS can be performed via sink and source places; source (sink) places are places having no input (output) arcs; in the source (sink) places command tokens are delivered by (got from) the dispatcher (Fig. 5). Further on we focus on some details about the integration of the subsystems. For example, concerning the communication between the OS and CRANEi ; the OS sends a sub-mission order by putting in place Psrfig (that is a source place) of the CRANEi model a token whose format is ðop; x; y; z; wÞ with




op: operation type (0 homing operation, 1 storage operation, 2 retrieval operation); x: x-coordinate of rack location; y: y-coordinate of rack location; z: rack location depth; w: rack side. 4.4. Operation time A CTPN is a CPN where a time delay is associated with each transition; such delay represents the time required to complete the firing. In this paper timed transitions, having a finite time delay and drawn by empty boxes, are used to model the vehicles travelling time and loading/unloading time. The time delay may be either constant, like for loading/ OPTIMIZER Psr{4} Psr{1} Psk{1} Psr{2} Psk{2} Psr{3} Psk{3} Psk{4} Part OUT Part IN BufferIN (i = 5) CRANE 1 (i = 1) CRANE 2 (i = 2) CRANE 3 (i = 3) Buffer OUT (i = 6) SHUTTLE (i=4) Pf{1} Pf{2} Pf{3} BayPR 1 (i = 7) Pf{4} Pf{5} BayPR 2 (i = 8) Pf{6} Pf{7} BayPR 3 (i = 9) Pf{8} Pf{9} BayPR 4 (i = 10) Fig. 5. Interaction between CTPN modules of the whole model and the optimizer sub-system. ARTICLE IN PRESS F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 unloading operations, or depending on the distance between the current position of the crane machine and the rack location of the pallet destination/location, for the retrieval/storage time. Immediate transitions, having a null time delay and drawn by bars, are used to model the logical activities and failure detection. An example of logical activity is the choice between storage, homing or retrieval missions which is modelled by a conflict between three immediate transitions: the start of each mission is conditioned by the value of the token color (the component Op of the token in place Pfi; 2g determines which of the three transitions Ts1i; Th1i; Tr1i is enabled, see Fig. 3.) 4.5. Distributed and modular design The interface among modules is performed via fusion places. Each fusion place is a set of places that are considered to be identical, i.e. they all represent a single conceptual place even though they are drawn as individual places. Fig. 5 represents the merging of the sub-models to obtain the whole model of the warehouse system depicted in Fig. 1. Note that for each sub-system present in the warehouse there is a corresponding submodel and the interfaces among the sub-modules are represented by fusion places. When a token is added to (removed from) one of these places, an identical token is added to (removed from) all other places in the fusion set. For example, let us consider more in detail the communication between the shuttle and the CRANEi during a delivering operation (see Figs. 3 and 4). As said, the command token format for place Pf f2ig is ðsh; bay; IDSU; comÞ where:



sh: shuttle identifier; bay: number of shuttle bay aligned with CRANEi input buffer; IDSU: stock unit identifier (pallet number); com: command to execute on pallet IDSU: (e.g. 0 nothing, 1 picking, 2 delivering) or mission status (e.g. -3 bay already busy, -2 buffer full, -1 end mission). In the shuttle model the com component is used to distinguish a delivering operation from a picking one. In the crane model the IDSU component is used to identify the pallet. Once the pallet has reached the position represented by place Pfi; 15 þ 4p  4g; it is possible to assign the correct coordinates of the destination to the crane machine (see the token format of place Pfi; 5g). Remark 2. To further clarify this point, we show how a loading/unloading operation can be executed only when the pallet colors and the buffer location place colors are 1231 matched. For example in the crane model (see Fig. 3), a pallet can be loaded on the input buffer if and only if: (a) the first location of the input buffer is free since a black token is present in place Pfi; 16g; (b) in place Pf f2ig token ðsh; bay; IDSU ; comÞ is present, i.e. bay bay of the shuttle is aligned with the input buffer; (c) guard ½prðPf f2ig; 4Þ ¼ 2 and prðPf f2ig; 3Þa0 associated with transition TbIi is true, i.e. the component com of the pallet token must correspond to a delivering operation ðprðPf f2ig; 4Þ ¼ 2Þ and the pallet is present on the shuttle bay ðprðPf f2ig; 3Þa0Þ: Notice that token ðIDSUÞ moves from place Pfi; 15g to place Pfi; 15 þ 4p  4g having no rack destination location. When transition TbIpi fires, token ðx; y; z; wÞ is merged with token ðIDSU Þ producing token ðx; y; z; w; IDSUÞ: This solution has been chosen in order to give the IDSU a rack destination location at the last moment, according to the CRANEi optimization policy. 5. Optimizer system architecture For the OS we propose the architecture shown in Fig. 6. Its inputs are mission queues, while its outputs are order (sub-mission) queues. All the missions created at the same time by level 2 MS are placed into the FIFO queue called Mission. First of all, the OS makes a separation between storage and retrieval missions. The storage missions are all saved in the Storage queue, which is composed of the missions starting from BufferIN and the missions whose starting point is on one of the picking/refilling bays. On the other hand, the retrieval missions have as their starting point a location in the rack. Therefore, for each aisle there is a different Retrievalfig queue. In general these queues are not FIFO since, on the basis of the implemented control policies, there could be a dynamic rescheduling of the missions depending on the plant state. From each mission, the following information are taken out: SU identifier (IDSU), starting point (SP) and end point (EP), as shown in Table 3. These information are transferred to the MissionSeg function which derives the basic sequences to be performed in order to move the SU from the SP to the EP, by segmenting the mission itself in basic handling sequences (Table 3). For example, as for the mission from BufferIN to Aislei ; the dispatcher produces the following orders (segments of mission):


a movement order for the Shuttle sub-system from its current position to the SP (BufferIN); a movement order for the Shuttle sub-system from the SP to the input buffer of Aislei ; a movement order for the CRANEi from its current position to its input buffer; ARTICLE IN PRESS 1232 F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 Fig. 6. Optimizer model.
a movement order for the CRANEi from its input buffer to the EP (Aislei rack location). As said, the OS core is the dispatcher block, in which the control policies are implemented. It decides the order of the mission segments to be executed, by dynamically rescheduling the missions inside the order queues. Therefore, the dispatcher controls the system progression by adding appropriate tokens to the source places of the shuttle and of the cranes (Psrfnt þ 1g and Psrfig; i ¼ 1; 2; 3) (see Fig. 6). The dispatcher bases its decisions also on the results of previous sequences assigned to the shuttle and the cranes (Pskfnt þ 1g and Pskfig; i ¼ 1; 2; 3). 6. Automated warehouse systems control: background The goal of this section is to propose an optimal strategy for improving the throughput of the warehouse; we focus first on the cranes/aisles sub-system and then on the shuttle sub-system. 6.1. The crane/aisle sub-system We abstractly assume to deal with a single aisle, onesided rack warehouse under the assumption that a DC cycle is adopted. For a single aisle one-sided rack warehouse, the throughput is defined as the inverse of the mean time required to perform the cycle; obviously, a simple way to improve the throughput could be that of reducing the dimension of the aisle, and therefore of the corresponding rack. However, in a real warehouse (consisting of two or more two-sided aisles), this approach would lead to build more aisles if one desires the storage capacity of the warehouse to remain unchanged. This way of proceeding requires further replication of expensive sub-systems and therefore should be avoided; in particular, in an automatic system, each aisle is equipped with its own crane, which generally mounts a rather expensive technology on-board. The above discussion leads to the following conclusion: it is mandatory to improve the throughput without reducing the rack dimension. From now on we shall make the following assumptions: A1 We deal with an SU system; an SU is regarded as an indivisible part (at least from the system point of view) of a certain product. The crane can carry one SU at the time (one in the storage phase and one in the retrieval phase). Each location of the rack can contain exactly one SU of the given product; A2 The crane travels simultaneously in both rack directions, with constant speed (acceleration and deceleration ramps are not considered); ARTICLE IN PRESS F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 1233 Table 1 Transition description of CRANEi CTPN model Table 2 Place description of CRANEi CTPN model Label Transition guard Label Token color—place interpretation Transition activity description Psrfig Pfi; 2g ðOp; x; y; z; wÞ—List of crane missions. ðOp; x; y; z; wÞ—The crane is waiting the choice of mission to be executed. ðx; y; z; wÞ—The crane is moving to the input buffer to pick up a pallet to be stored at location ðx; y; z; wÞ ðx; y; z; wÞ—The crane is waiting for a pallet from the input buffer ðx; y; z; w; IDSUÞ—The crane is moving to location ðx; y; z; wÞ with pallet IDSU ðx; y; z; w; IDSUÞ—The crane is delivering the pallet at location ðx; y; z; wÞ ð1Þ—The crane is going back to the home position ð1Þ—End mission ðx; y; z; wÞ—The crane is moving to location ðx; y; z; wÞ to execute a retrieval operation ðx; y; z; wÞ—The crane is picking up a pallet from rack location ðx; y; z; wÞ ðIDSUÞ—The crane is moving to the output buffer with pallet IDSU ðIDSUÞ—The crane is delivering the pallet IDSU to the output buffer ð1Þ—Crane ready to execute a new mission ðsh; bay; IDSU; comÞ—Bay ‘‘bay’’ of shuttle aligned with input buffer delivery station ðIDSUÞ—Pallet IDSU is on the input buffer ð1Þ—State of input buffer locations (if marked the associated location is empty) ðsh; bay; IDSU; comÞ—Bay ‘‘bay’’ of shuttle aligned with output buffer picking station ðIDSUÞ—Pallet IDSU is on the output buffer ð1Þ—State of output buffer locations (if marked the associated location is empty) ðemÞ—Mission result Topi Absent Start crane mission. Ts1i ½prðPfi; 2g; 1Þ ¼ 1 Start storage mission Ts2i Absent The crane is moving to the input buffer TbIpi Absent The crane is loading the pallet from input buffer Ts3i Absent The crane is moving to the rack location Ts4i Absent The crane is delivering the pallet Th1i ½prðPfi; 2g; 1Þ ¼ 0 Start homing mission Th2i Absent The crane is going back to the home position Tr1i ½prðPfi; 2g; 1Þ ¼ 2 Start retrieval mission Tr2i Absent The crane is moving to the rack location Tr3i Absent The crane is picking up the pallet from the rack location Tr4i Absent The crane is moving to the output buffer TbO1i Absent The crane is delivering the pallet TbOji Absent j ¼ 2::p A pallet is moving to the next output buffer location TbOi ½prðPf f2i þ 1g; 3Þ ¼ 0 and prðPf f2i þ 1g; 4Þ ¼ 1 The shuttle bay is free and there is a load command A pallet is moving onto the shuttle bay from the output buffer TnOi ½prðPf f2i þ 1g; 3Þa0 and prðPf f2i þ 1g; 4Þ ¼ 1 The shuttle bay is not free and there is a load command Error detection TbIji Absent j ¼ 1::p  1 A pallet is moving to the next input buffer location TbIi ½prðPf f2ig; 4Þ ¼ 2 and prðPf f2ig; 3Þa0 Shuttle bay loaded and there is an unload command A pallet is moving onto the input buffer from the shuttle bay TeOi Absent End crane mission TnIi ½prðPf f2ig; 4Þ ¼ 2 Unload command Watchdog timer A3 Storage assignment is performed by the upper level and the policy is unknown; to evaluate our algorithms we suppose that a completely random storage assignment is used. This means that no specific rule is followed when assigning a storage location to an incoming SU; the problem of throughput optimization under more sophisticated storage strategies (for example class based (Hausman, Schwarz, & Graves, 1976)) will be discussed in future papers; Pfi; 3g Pfi; 4g Pfi; 5g Pfi; 6g Pfi; 7g Pfi; 8g Pfi; 9g Pfi; 10g Pfi; 11g Pfi; 12g Pfi; 13g Pf f2ig Pfi; 15 þ ð4j  4Þg j ¼ 1::p Pfi; 15 þ ð4j  3Þg j ¼ 1::p Pf f2i þ 1g Pfi; 15 þ ð4j  2Þg j ¼ 1::p Pfi; 15 þ ð4j  1Þg j ¼ 1::p Pskfig A4 The rack is continuous; this means that it is composed of an infinite number of virtual locations. Each location is addressed by a pair of real numbers. Remark 3. Assumption A4 is standard in the study of warehouse systems (see for example, Graves, Hausman, & Shieh, 1977; Bozer & White, 1984). Indeed it is not possible to develop a general theory if we try to take into account the discrete nature of the rack structure. The following notation will be used:




sh sv L H th horizontal speed of the crane [m/min] vertical speed of the crane [m/min] rack length [m] rack height [m] L=sh time to reach the horizontal end of the rack [min] ARTICLE IN PRESS F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 1234 Table 3 Possible missions in lay-out of Fig. 1 SP EP BufferIN Aislei rack location Aislei rack location BayPRj Aislei rack location BayPRj
E½TB BufferOUT
tC Aislei rack location
tW
E½DC C  Table 4 Coefficients of the function d k ðbÞ k a0 a1 a2 a3 a4 a5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0.4997 0.3336 0.2503 0.1993 0.1663 0.1422 0.1245 0.1114 0.0999 0.0904 0.0825 0.0764 0.0712 0.0662 0.0622 0.0584 0.0551 0.0519 0.0494 0.0471 0.4864 0.5136 0.4968 0.4615 0.4376 0.3980 0.3737 0.3503 0.3137 0.2839 0.2518 0.2300 0.2109 0.1834 0.1687 0.1469 0.1308 0.1116 0.1006 0.0867 0.4237 1.1575 1.5516 1.7505 1.9227 1.9223 1.9613 1.9492 1.8515 1.7755 1.6601 1.5835 1.5145 1.3838 1.3286 1.2216 1.1479 1.0574 1.0039 0.9283 0.1586 1.0501 1.9574 2.5666 3.1653 3.3451 3.5894 3.6822 3.5835 3.5201 3.3441 3.2365 3.1397 2.8832 2.8057 2.5918 2.4591 2.2877 2.1874 2.0307 0.1525 0.5085 1.2351 1.8095 2.4564 2.6994 3.0003 3.1439 3.1070 3.1010 2.9727 2.9048 2.8425 2.6121 2.5649 2.3682 2.2594 2.1111 2.0245 1.8795 0.0202 0.0811 0.2876 0.4742 0.7127 0.8114 0.9296 0.9917 0.9916 1.0025 0.9670 0.9526 0.9380 0.8611 0.8518 0.7844 0.7514 0.7037 0.6756 0.6263 NS bS  100% 2 3 4 5 6 7 8 9 10 3.4084 5.6305 7.2506 8.5113 9.5347 10.3904 11.1218 11.7575 12.3176 tv

T b
E½SC Without loss of generality we assume that th otv ; therefore the rack is the rectangular region depicted in Fig. 7(a). If we locate the I/O point at the left-lower corner of the rack and fix a pair of coordinate axis with origin at the I/O point, the rack region can be identified with the set of points belonging to the interval ½0; b ½0; 1: According to Fig. 7(b), it is simple to recognize that E½DC C  can be computed according to the following expression: E½DC C  ¼ E½SC þ E½TB þ E½SC ¼ 2E½SC þ E½TB: In Bozer and White (1984) it is shown that   1 1 2 þ b T; E½SC ¼ 2 6   1 1 2 1 3 þ b  b T: E½TB ¼ 3 6 30 Table 5 Behavior of bS versus N S
from the I/O point (the retrieve location) to the storage location (the I/ O point) [min] expected time for Travel-Between (TB), i.e. time to travel from the storage location to the retrieve location [min] time the crane needs to store or retrieve an SU [min] average time the crane has to wait at the aisle input buffer for an incoming SU [min] expected time for the crane DC cycle [min]. H=sv time to reach the vertical end of the rack [min] maxfth ; tv g [min] minfth =T; tv =Tg rack shape factor (adimensional) expected time for the crane Single Command (SC) cycle, i.e. time to travel Therefore, from (1) we have   4 1 2 1 3 þ b  b T: E½DC C  ¼ 3 2 30 ð1Þ (2a) (2b) (3) If we consider a set of n DC cycles the crane throughput gC is defined as 2n nE½DC C  þ 4ntC þ ntW 2 ¼ : E½DC C  þ 4tC þ tW gC ¼ ð4Þ Now let us assume obtaining a reduction of the travelbetween (TB) time equal to a  100%; the new throughput can be written as g~ C ¼ 2 : E½DC C   aE½TB þ 4tC þ tW (5) Obviously, g~ C 4gC ; therefore we let g~ C ¼ ð1 þ bC ÞgC ; where bC  100 represents the percentage throughput ARTICLE IN PRESS F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 improvement. We have g~ C  gC gC E½DC C  þ 4tC þ tW ¼  1: E½DC C   aE½TB þ 4tC þ tW bC ¼ ð6Þ Remark 4. Note that bC depends on the design parameters b, th and tC which, for a given warehouse, are fixed, and on the optimization parameters a and tW ; a is increased when the TB time is optimized, while tW is reduced when the shuttle operations are optimized. Remark 5. It is important to recall that, while the values of E½DC C ; E½TB are exactly evaluated in (2b) and (3), the value tc is known and a will be evaluated in the next section, the parameter tW can only be evaluated via simulation and therefore only when a whole model of the warehouse is available. In Fig. 8 the behavior of the function bC ðaÞ parameterized in tW is depicted for b ¼ 0:316; th ¼ 1235 0:360 and tC ¼ 0:04 (these are the parameter values of the real warehouse system we shall consider later in the paper). Note that, as expected, bC is an increasing function of a and a decreasing function of tW : We note that for tW ¼ 0:5 a TB time reduction of 60% (that is a ¼ 0:6) corresponds to a throughput improvement of 12%; which, according to Han, McGinnis, Shieh, and White (1987), leads in a large warehouse, to the elimination of an aisle without reducing the overall warehouse performance. Also note that in correspondence to a smaller tW there is a strong improvement of the throughput; for example for tW ¼ 0:2 we have that bC 40:14: 6.2. The shuttle sub-system We assume that the shuttle cycle is composed of a picking operation followed by a deposit operation. Therefore, also in the shuttle case, we talk of DC cycle. We make the following further assumptions: A5 The shuttle travels with constant speed; A6 Along the mono-dimensional path of the shuttle there is a continuous distribution of picking/deposit location; we place the origin of the path abscissa in correspondence of the main input buffer and the end in correspondence of the main output buffer. The following notation will be used:
Fig. 7. (a) Rack shape; (b) Computation of E½DC: sS speed of the shuttle [m/min] 0.18 0.16 τw=0.0 βC (α) parameterized in τw 0.14 τ =0.1 w τ =0.5 w τ =0.6 w τ =0.3 τ =0.7 w w τ =0.4 τw=0.8 w τ =0.9 w τw=1.0 0.12 τw=0.2 0.1 0.08 0.06 0.04 0.02 0 0.2 0.3 0.4 0.5 α 0.6 Fig. 8. Behavior of bC ðaÞ parameterized in tW : 0.7 0.8 ARTICLE IN PRESS F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 1236

LS tS
E½P
E½D
tS
E½DC S  length of the shuttle path [m] LS =sS time to go from the origin of the path to the end of the path [min] expected time to go from a given point to the next picking location [min] expected time to go from the picking location to the next deposit location [min] (E½P ¼ E½D when no optimization algorithm is used) time the shuttle needs to pick up or deposit an SU [min] expected time to go from a given point to the deposit location in the shuttle DC cycle [min] (E½DC S  ¼ 2E½P ¼ 2E½D when no optimization algorithm is used). At the moment, we assume to have a sequence of n pair of pick-up and deposit orders LIST ord ¼ fðPi ; Di Þ; i ¼ 1; . . . ; ng; where Pi and Di denote the location of the ith pick-up and deposit, respectively, and to follow a FIFO policy; therefore each pair ðPi ; Di Þ is executed according to the ordered list LIST ord : In this case we have E½DC S  ¼ E½P þ E½D ¼ 2E½P: (7) E½P ¼ 13 tS ; @Gðx; zÞ ¼ > 1; @z > > : 0; zo0; 0ozox; xo1  x; z41  x (12) The expected value, EðxÞ; of the distance of an arbitrary chosen point in the interval ½0; 1 from x 2 ½0; 12 is therefore given by EðxÞ ¼ Z 1x 0 1 zgðx; zÞ dz ¼ x2  x þ : 2 (13) By symmetric arguments, it is simple to recognize that EðxÞ; for x 2 ½12; 1; has the same expression as (13). Therefore, by integrating over x, we obtain E½P as follows E½P ¼ 2tS Z 1=2 EðxÞ dx ¼ 0 1 tS : 3 (14) 6.3. A performance index for the whole warehouse (8) 2 E½DC C  þ 4tC þ tW gC ¼ therefore, from (7) we have (15) and the shuttle/picking refilling sub-system throughput E½DC S  ¼ 23 tS : (9) Therefore, when no optimization is performed, the shuttle throughput is 2 3 ¼ : E½DC S  þ 2tS tS þ 3tS (10) To prove formula (8), without loss of generality, we consider a path of unit length; the final result will be then multiplied by tS : Let us denote by x 2 ½0; 12 the position of the picking location. Denote by Zx the stochastic variable whose realization represents the distance of an arbitrary chosen point of the interval ½0; 1 from the point x. The probability density function (pdf) Gðx; zÞ of Zx is given by 8 0; > > > < 2z; Gðx; zÞ:¼ProbðZ x pzÞ ¼ > z þ x; > > : 1; gðx; zÞ:¼ 8 0; > > > < 2; So far we have introduced two partial performance indices: the crane/aisle sub-system throughput In the sequel we shall show that gS ¼ Therefore the cumulative distribution function (cdf) gðx; zÞ has the following expression: zo0; 0ozox; xozo1  x z41  x: (11) gS ¼ 2 : E½DC S  þ 2tS (16) From the above formulae it is evident that an improvement of the crane throughput gC can be obtained, as observed in Section 6.1, via the reduction of E½DC C ; in the same way an improvement of the shuttle throughput gS can be obtained by reducing E½DC S ; note that the improvement of gS also brings a benefit to the index gC through the reduction of tW : In any case, from the point of view of the indices defined above, the crane and shuttle optimizations can be performed independent of each other. Now we shall introduce a further index which looks at the warehouse as a whole. This index is a measure of the warehouse system throughput, since it considers complete missions, starting from the main input buffer and ending at the main output buffer or at some of the rack locations. This index is defined as follows: number of complete operations : (17) time From the point of view of index (17) there is interaction between the crane and shuttle optimizations. gW ¼ ARTICLE IN PRESS F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 For this reason the separate optimization of the two sub-systems leads to a sub-optimization of index (17).3 On the other hand, finding an optimization policy which looks at the system as a whole is a very complex objective (and may be not achievable by simple strategies), and is beyond the scope of this paper. According to the above considerations, in the sequel we shall develop two strategies: (i) reduction of the TB time in order to minimize E½DC C ; i. e. to maximize the parameter a introduced in Section 6.1; (ii) reduction of tW by optimization of the shuttle operations. The impact of the optimization policies on the index (17) will be a posteriori evaluated in Section 9. 7. An optimization algorithm for the crane/aisle subsystem In this section we shall describe the proposed optimization policy, under the following further assumption. A7 Each SU arrives at the I/O point with the storage location already assigned. Due to Assumption A7, the only degree of freedom, in the optimization procedure, is the clever sequencing of the retrieval orders. The approach followed in this paper can be roughly described as follows: consider a list of N C storage and retrieval orders; optimize the sequencing of the N C retrievals; when the N C DCs have been performed consider a new list of N C orders and repeat the same procedure. This approach belongs to the category of the so-called static approaches. An alternative way to proceed, which is not considered here, is known in the literature as the dynamic approach (Seidmann, 1988; Linn & Xie, 1993). It consists of resequencing the list of orders whenever a new pair storage/ retrieval is available; in this case it is necessary to assign due dates to the retrievals, to avoid that retrievals from locations at the end of the rack are never executed. To describe the algorithm we propose, let us denote by R the set composed of the retrieval location addresses, by S the ordered list of storage location addresses and by N C the cardinality of R and S. Algorithm 1. S1 Take the first element s 2 S: Select the element of R with the minimum TB distance from s measured by the Chebichev metric. Recall that, given two points P1 ¼ ðx1 ; y1 Þ and P2 ¼ ðx2 ; y2 Þ; the Chebichev distance d C ðP1 ; P2 Þ between P1 3 Simulation experiments show that an almost perfect decoupling between crane and shuttle optimizations is reached for very small values of tW : 1237 and P2 is defined as d C ðP1 ; P2 Þ:¼ maxfjx1  x2 j; jy1  y2 jg: We need to use Chebichev metric because the crane moves simultaneously in both directions. S2 Perform the DC cycle with storage in s and retrieval from r. S3 Update R ¼ R  frg; S ¼ S  fsg: S4 If R ¼ ; then stop; otherwise goto Step S1. The performance of an optimization procedure similar to Algorithm 1 has been evaluated in Han, McGinnis, Shieh, and White (1987). However, in that study it was assumed that the destination address of the incoming SU could be chosen among a number of empty locations; moreover, the theoretical computation of the expected performance of that procedure was obtained in an approximate way. The aim of this section is that of computing exactly the expected performance of the procedure described in Algorithm 1 under the Assumptions A1–A4, A7. This result will be then validated in Section 9 on a real warehouse. Note that, at step S1 of Algorithm 1, it is chosen, between the elements of R, the one which guarantees the minimum distance between the storage address and the retrieval address. Therefore the first question to be answered is the following: What is the expected mean value d k ðbÞ of the distance between a point in the rectangular region ½0; b ½0; 1 and the nearest (in the Chebichev sense) of k arbitrary chosen points in the same region? Experience (see formulae (2a)–(2b)) suggests that average distances typically are polynomial functions of the shape factor b. Therefore, we assume the following structure for the function d k ðbÞ: d k ðbÞ ¼ a0k þ a1k b þ a2k b2 þ a3k b3 þ a4k b4 þ a5k b5 : (18) Moreover, note that a fifth-order polynomial is, in any case, a very good approximation of any continuous function around zero (remember that b 2 ð0; 1Þ). In (Amato & Basile, 2002) a procedure which makes use of a parametric identification based method to evaluate the coefficients of the vector ak ¼ ða0k a1k a2k a3k a4k a5k ÞT has been presented. By applying this procedure we found the coefficients for d̄ k ðbÞ; k ¼ 1; y, 20, reported in Table 4. 8. An optimization algorithm for the shuttle sub-system The goal of this sub-section is the development of an optimal strategy for improving the throughput of the ARTICLE IN PRESS F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 1238 sub-system composed by the shuttle and the picking/ refilling locations. The proposed algorithm makes a clever sequencing of the scheduled picking/deposit operations to improve the throughput of the shuttle system. Algorithm 2. (See Section 6.2 for the notation) distance of an arbitrary chosen picking location from the starting point x 2 ½0; 1=2 plus the distance of an arbitrary chosen deposit location from the picking location. The cdf G O ðx; zÞ of the stochastic variable Z O x has the following expression: G O ðx; zÞ S0 (Initialization) Choose N S such that n=N S ¼: nbatch 2 N: Let START ¼ The initial location of the shuttle COUNT ¼ 0: S1 Consider the first N S elements of LIST ord ; ðPi ; Di Þ; i ¼ 1; . . . ; N S : Let N left ¼ N S LIST ¼ fðPi ; Di Þ; i ¼ 1; . . . ; N left g LIST ord ¼ LIST ord  LIST: S2 Compute: DIST i ¼ distðSTART; Pi Þ þ distðPi ; Di Þ i ¼ 1; . . . ; N left : k ¼ argmin DIST i i¼1;...;N left Pcurr ¼ Pk Dcurr ¼ Dk : S3 Execute ðPcurr ; Dcurr Þ: Let START ¼ Dcurr N left ¼ N left  1 LIST ¼ LIST  fðPcurr ; Dcurr Þg COUNT ¼ COUNT þ 1: S4 if N left a0 goto Step S2; elseif COUNT onbatch goto Step S1; else end of the algorithm. :¼ProbðZO x pzÞ 8 0; > > > > > > 2z2 ; > > > > > 3 2 3 1 2 > > 4 z þ 2 xz  4 x ; > > > > <  12 z2 þ 32 z  12 x2 ¼ > þ 12 x  14 ; > > > > > > >  14 z2 þ  12 x þ 1 z > > > > > þ  14 x2 þ x ; > > > > : 1; zo0; 0pzox; xpzo1  x; 1  xpzo1 þ x; : ð19Þ 1 þ xpzo2  x; zX2  x: The corresponding pdf is gO ðx; zÞ d :¼ G O ðx; zÞ dz 8 0; > > > > > > 4z; > > > > > < 32 z þ 32 x; ¼ > z þ 32 ; > > > > > > >  12 z þ  12 x þ 1 ; > > > : 0; zo0; 0pzox; xpzo1  x; 1  xpzo1 þ x; ð20Þ 1 þ xpzo2  x; zX2  x: Now, by ZO x;k we denote the stochastic variable whose realization represents the minimum between k distances (corresponding to k picking/deposit pairs) starting by point x. It is simple to recognize that the pdf of Z O x;k is given by k O GO k ðx; zÞ ¼ 1  ð1  G ðx; zÞ Þ: (21) Remark 6. Note that Pi ’s represents the coordinates of the buffer locations where the SUs have to be picked and Di ’s the coordinates of the buffer locations where the SUs have to be stored; therefore, in order to implement the control algorithm described above, the knowledge of current position of the shuttle is necessary. Therefore, as in the classical control context, the control algorithm we finally use is state dependent. Therefore the expected travel time, starting from x, corresponding to the minimum travel time between k possible picking/deposit pairs is To evaluate analytically the expected time to execute a DC under the application of Algorithm 2, let us assume to deal with a unit length path and denote by ZO x the stochastic variable whose realization represents the EO k ½DC S ðxÞ Z 2x ¼ tS zkð1  G O ðx; zÞÞk1 gO ðx; zÞ dz: From (21) it is possible to derive the cdf of Z O x;k d O G ðx; zÞ dz ¼ kð1  G O ðx; zÞÞk1 gO ðx; zÞ: k1 O gO k ðx; zÞ ¼ kð1  G ðx; zÞÞ 0 ARTICLE IN PRESS F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 Finally, by integration over x, we obtain E O k ½DC S ; the expected time to perform a shuttle DC cycle by choosing among k picking/deposit pairs the one with minimum travel time from an arbitrary starting point in ½0; 1 Z 1=2 EO ½DC  ¼ 2 EO S k k ½DC S ðxÞ dx: 0 Now if we have a block of N S picking/deposit pairs, the first time we select the minimum between N S distances, the second time the minimum between N S  1 distances, etc. Therefore the expected time to perform a set of N S DC cycles, in presence of optimization, is given by PN S O k¼1 E k ½DC S  : (22) EO ½DC  ¼ S N NS Now the shuttle throughput in presence of optimization is given by



To test our algorithm we have integrated it with the CTPN model of the real warehouse as developed in the first part of the paper. A simulation experiment has been conducted under the following assumptions.

therefore, the shuttle throughput improvement bS is given by g~ S  gS 2 tS þ 3tS ¼  1; gS 3 EO ½DC S  þ 2tS N where E O N ½DC S  is given by (22). In Table 5 the values of bS for N S ¼ 2; 3; . . . ; 10; tS ¼ 0:067 and tS ¼ 0:181 (these are the parameter values of the real warehouse system we shall consider later in the paper) are reported. 9. Case study: control of a medium-size warehouse In this section we refer to the automated warehouse of a real plant. The main characteristics of the warehouse model are the following:








sh ¼ sv ¼ 50 ½m= min; rack location size¼ 1 ½m 1 ½m 1 ½m; number of x location¼ 18; thus L ¼ 18 ½m; number of y location¼ 57; thus H ¼ 57 ½m; speed of shuttle machine ss ¼ 100 ½m= min; length of the shuttle path LS ¼ 18:10 ½m; time to move the SU to the next buffer position tB ¼ 0:083 ½min; time to load/unload the pallet on the crane machine tC ¼ 0:04 ½min; time the shuttle needs to load/unload a pallet tS ¼ 0:067 ½min: Note that, according to the notation of Section 6, we have:
th ¼ 0:36 ½min; tv ¼ 1:14 ½min; T ¼ tv ¼ 1:14 ½min; b ¼ 0:316; tS ¼ 0:181 ½min: 9.1. Simulation results 2 g~ s ¼ O ; E N ½DC S  þ 2tS bS ¼ 1239

A number of 120 complete DC missions is considered. In this set of missions a number of 40 complete DC missions is considered for each crane machine. A complete DC mission consists of a storage mission starting from the first location of the main input buffer or from a picking/refilling area output location and terminating at an aisle rack location and of a retrieval mission starting from an aisle rack location and terminating at the last location of the main output buffer or at a picking/refilling area input location. A partial DC mission consists of the part of a complete mission which starts at the input buffer of the aisle and terminates at the output buffer of the same aisle (this is the classical DC cycle considered in Section 6.1). The experiment is repeated a number of times by permuting the list of storage orders S. For each set of the 40 complete DC missions, two simulation experiments, according to Algorithm 1 with N C ¼ 1 and 20, have been executed. In both simulations we did not perform the shuttle optimization. We denote by DC N C ¼1 and DC N C ¼20 the average time to perform a partial DC mission in the two cases. We obtained DC N C ¼1 ¼ 2:80; DC N C ¼20 ¼ 2:53; tW ¼ 0:9: Now let us compare the theoretical and simulation results. According to the theory developed in Section 6.1, in the case of one-sided aisle and b ¼ 0:3 we have that a20 ð0:3Þ ¼ 0:69 (see Fig. 9). From Fig. 8 we have that the theoretical improvement bC of the throughput should be about 11% (for tW ¼ 0:9 and a ¼ 0:69). Concerning the simulation results, taking into account that the computed average time to perform a simulated partial DC cycle also incorporates the term 4t þ tW ; we have (see formulae (4)–(6)) gC ¼ 2 2 ¼ 0:714; ¼ DC N C ¼1 2:80 ARTICLE IN PRESS F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 1240 Therefore, concerning the throughput improvement of the whole warehouse, we have 0.7 b=0.3 0.6 b=0.5 b=0.7 α N (b) parameterised in b bW  100% ¼ 0.5 b=0.9 0.4 0.3 0.2 0.1 0 0 2 4 6 8 10 12 14 16 18 20 N Fig. 9. Behavior of aN ðbÞ parameterized in b. g~ C ¼ 2 DC N C ¼20 ¼ 2 ¼ 0:791: 2:53 Therefore, the real improvement is bC  100% ¼ g~ C  gC  100% ¼ 10:8% gC which is in accordance with the theoretical result. For the same sets of DC missions considered above, we have executed another simulation experiment in which also the shuttle optimization has been considered; indeed Algorithm 2 with N S ¼ 5 has been applied. We denote by DC N C ¼20;N S ¼5 the average time to perform a partial DC mission in this case. We obtained DC N C ¼20;N S ¼5 ¼ 2:42; tW ¼ 0:5: Thus we have g~ 0 C ¼ 2 DC N C ¼20;N S ¼5 ¼ 2 ¼ 0:826: 2:42 In this case the real improvement is 0 bC  100% ¼ g~ 0 C  gC  100% ¼ 13:6% gC g~ W  gW  100% ¼ 12:8%: gW In order to test the algorithm on the real architecture to be used on the plant, the test bed represented in Fig. 10 has been built. The plant low-level control is performed by the Handling Systems which is a Programmable Logic Controller connected to a process emulator via Profibus DP. The Management System is the upper level which sends storage and retrieval missions, where storage locations are specified. The optimizer system has been implemented in the C++ language and interfaced with the Management System and Handling System, according to the architecture described in the first part of the paper. It has been executed on a Personal Computer with a Pentium III processor at 800 MHz and 512 Mb of RAM on board. The purpose of these further tests is to show that some approximations used in algorithm synthesis, e.g. neglecting the communication delays and the computation times, do not affect system performances. Test bed validation results have confirmed the validity of these approximations. Finally, simulation results as well as test bed validation results have been confirmed by the application of the proposed architecture and control algorithms to the real automated warehouse in the sense that no considerable difference has been measured in the real automated warehouse. 10. Conclusions The introduction of a new level, the OS, in the control architecture of warehouse systems has been illustrated. In this way it is possible to separate handling from short-term optimization. The development, as well as the testing and debugging, of handling sequences code is very simplified; the basic sequences code is very similar for different warehouse systems, so its reuse is easily achieved. In addition, the OS can be developed and which is in accordance with the theoretical result, obtained by looking at Fig. 8 with a ¼ 0:69 and tW ¼ 0:5: Concerning the throughput improvement index (17) associated with the global optimization of the warehouse, we compare the case in which no optimization is performed (N C ¼ 1; N S ¼ 1) with the full optimization case (N C ¼ 20; N S ¼ 5); we obtain gW ¼ 0:465; g~ W ¼ 0:525; where gW and g~ W are the throughputs before and after the optimization, respectively. Fig. 10. Testing environment architecture. ARTICLE IN PRESS F. Amato et al. / Control Engineering Practice 13 (2005) 1223–1241 tested using simulations of the plant since a detailed model of the plant—as controlled by handling sequences code—is available. CTPNs have resulted to be an effective tool for automated warehouse modelling. The main problems encountered in modelling such systems (resource attributes, higher level scheduler integration, operation time, modular design) can be solved by using a unique formal model. This makes possible to test the whole control architecture of an automated warehouse and to work on the same model for the development of complex control strategies and the on-line plant monitoring. The availability of a detailed model opens the door to the implementation of fault detection functions, after failures—not considered in this paper—have been modelled, as well as to the application of modern optimization techniques to the warehouse low-level control field, thus obtaining more efficient warehouse control systems. In this paper, we have proposed two control algorithms to manage the cranes and the shuttle movements; the expected performance of such control algorithms has been derived under the simplifying assumption that the distribution of the locations within the warehouse is continuous; such assumption is standard in the warehouse system context and is necessary in order to obtain general results holding for any rack shape and depending on a few meaningful parameters. The evaluation of the control system performance on a real world warehouse, both validates the theoretical analysis previously obtained and shows the effectiveness of the proposed control algorithms. Open problems which are not discussed in this paper and will be investigated in future works are: (i) Use of the cranes optimization algorithm in a dynamic way, but assigning due dates to the retrieval orders. (ii) Development of control algorithms which take into account the different working conditions of the warehouse. Indeed it may happen that a set of only retrieval orders or only storage orders can be assigned from the high-level scheduler; in this case by using an ad hoc algorithm better results could be achieved. References Amato, F., & Basile, F. (2002). Crane and shuttle optimization in warehousing systems. 2002 IEEE International Conference on Robotics and Automation (ICRA’02). 1241 Basile, F., Carbone, C., & Chiacchio, P. (2001). Modeling of as/rs via coloured petri nets. IEEE International Conference on Advanced Intelligent Mechatronics (AIM 01). Basile, F., Carbone, C., & Chiacchio, P. (2003). An approach to control automated warehouse systems. IEEE international conference on computational engineering in systems applications (CESA’03). Bozer, Y. A., & White, J. A. (1984). Travel-time models for automated storage/retrieval systems. IEE Transactions, 16(4), 329–338. Chincholkar, A. K., & Krishnaiah Chetty, O. V. (1996). Simultaneous optimization of control factors in automated and retrieval systems and FMS using stochastic coloured Petri nets and the Taguchi method. The International Journal of Advanced Manufacturing Technology, 12, 137–144. DiCesare, F., Harhalakis, G., Proth, J. M., Silva, M., & Vernadat, F. B. (1993). Practice of petri nets in manufacturing. London: Chapman and Hall. Feldmann, K., & Colombo, A. W. (1999). Monitoring of flexible production systems using high-level Petri net specifications. Control Engineering Practice, 7, 1449–1466. Graves, S. C., Hausman, W. H., & Schwarz, L. B. (1977). Storageretrieval interleaving in automatic warehousing systems. Management Science, 23(9), 935–945. Han, M. H., McGinnis, L. F., Shieh, J. S., & White, J. A. (1987). On sequencing retrievals in an automated storage/retrieval system. IEE Transactions, 19(3), 56–66. Hausman, W. H., Schwarz, L. B., & Graves, S. C. (1976). Optimal storage assignment in automatic warehousing systems. Management Science, 22(6), 629–638. Hsieh, S., & Chen, Y. F. (1999). Agvsimnet: A Petri-net-based agvs simulation system. The International Journal of Advanced Manufacturing Technology, 15, 851–861. Hsieh, S., Hwang, J. S., & Chou, H. C. (1998). A Petri net based structure for AS/RS operation modeling. International Journal of Production Research, 36(12), 3323–3346. Jensen, K. (1995). Colored Petri nets. Basic concepts, analysis methods and practical use. Volume 1. Monographs on theoretical computer science. New York: Springer. Lee, H. F., & Schaefer, S. K. (1996). Retrieval sequencing for unit-load automated storage and retrieval systems with multiple openings. International Journal of Production Research, 34(10), 2943–2962. Lee, S. G., de Souza, R., & Ong, E. K. (1996). Simulation modelling of a narrow aisle automated storage and retrieval system (AS/RS) serviced by rail-guided vehicles. Computers in Industry, 30, 241–253. Linn, R. J., & Xie, X. (1993). A simulation analysis of sequencing rules in a pull-based assembly facility. International Journal of Production Research, 31(10), 2355–2367. Murata, T. (1989). Petri nets: Properties, analysis and applications. Proceedings of IEEE, 77(4), 541–580. Ramaswamy, S., & Valavanis, K. P. (1994). Modeling, analysis and simulation of failures in a material handling systems with extended Petri net. IEEE Transactions on System, Man and Cybernetics, 24(9), 1358–1373. Seidmann, A. (1988). Intelligent control schemes for automated storage and retrieval systems. International Journal of Production Research, 26(5), 931–952. Silva, M., & Teruel, E. (1997). Petri nets for the design and operation of manufacturing systems. European Journal of Control, 3(3), 182–199. Van den Berg, J. P. (1999). A literature survey on planning and control of warehousing systems. IIE Transactions, 31, 1–13.