AN EVALUATION OF ALTERNATIVE CONTROL STRATEGfESAND DESIGN ISSURE FOR AUTOMATED ORDER ACCUMULATIONAND SORTATION SYSIEMS Yavuz A. Rozer Industrial and Operations Engineering University of Michigan, Ann Arbor Marco A. Quiroz Industrial Engineering Eastman Kodak, Rochester Gunter P. Sharp Industrial and Systems Engineering Georgia Institute of Technology, Atlanta Technical Report 87-30 December 1987

ABSTRACT This study is concerned with performance analysis of a widely used concept in high volume sortation systems. Items are sorted using a loop conveyor equipped with automated mechanisms diverting into sortation lanes. Various control strategies and design issues are empirically examined using simulation under different assumptions concerning the pattern of the incoming stream of items to be sorted. Many of the results are robust, in the sense of being applicable over a wide range of conditions. The study differs from an earlier, related one with respect to the relationships between the number of orders processed per day and the number of sortation lanes available. I. INTRODUCTION Order accumulation/sortation (OA/S) systems are used in many warehousing and distribution applications where order picking is performed. The OA/S function generally includes all the material handling operations aimed at physically "bringing together" the items (tote bins or cartons) associated with the same order. Such operations are typically required prior to packing the items or palletizing/shipping the itemis associated with a particular order. Various methods and concepts are currently used in industry for order picking. Picking one order at-a-time, batch picking, zone picking, and pick-to-pack systems are among the most widely used concepts. Each concept presents certain advantages and limitations for the entire order picking operation, including the accumulation/sortation workload. For a discussion of the above concepts the reader is referred to Wilson and DeMaria [11]. OA/S systems may be classified for analysis purposes into two types: OA/S-1: used when accumulating and sorting the items of a relatively large number of small orders or shipments. OA/S-2: used when accumulating and sorting the items of a relatively small number of large orders or shipments. Typical applications of OA/S-1 would be an automobile parts distributor supplying individual service centers, a book distributor supplying individual bookstores, and a pharmaceutical distributor supplying individual drugstores. The typical order size is likely to be less than 35 cu. ft. (1.0 cu.m.). The items in the order may consist mainly of items retrieved in a splitcase pick area (retrieval of less-than-case lots) with some full cases and large, bagged items. Tote bins are frequently used to 2

facilitate order picking, accumulation, and sortation. After all the items of an order have been brought together, they are usually dispatched in overpack cartons (containing a number of diverse, consolidated articles), tote bins (containing diverse, consolidated items), full cases, large bags, or a combination of these. Palletizing is an option frequently selected at this point. A typical application of OA/S-2 would be a corporate warehouse supplying department stores belonging to the same corporate organization. The typical order size is likely to be nearly a truckload. The items of an order or shipment to be brought together may consist mainly of full cases, sealed overpack cartons, sealed tote bins, and other items. Both OA/S-1 and OA/S-2 may exist in one facility, as shown in the example depicted in Figure 1. OA/S-1 is used when the order or a part of it must be filled through split-case picking. The primary purpose of OA/S-1 in this example is to consolidate and verify all the split-case items picked for a particular order before they are packed in overpack cartons or tote bins. Thus, incoming items are sorted into "packing lanes". It is not unusual for the number of orders to exceed the number of lanes. OA/S-2, on the other hand, is used in this example primarily for sorting incoming items into "shipping lanes" which hold the cartons before they are palletized and/or loaded on the trucks. Note from Figure 1 that OA/S-2 is also used for merging the items of an order that may have required both full-case and split-case picking. In OA/S-2 the number of orders or shipments is usually less than or equal to the number of lanes. The type of material handling system used and the appropriate level of automation for OA/S-1 and OA/S-2 will vary from one application to another. The differentiation made above between OA/S-1 and OA/S-2 should not be interpreted as implying that a well-defined boundary exists between these two types. Nor should the reader infer that these two represent all accumulation/sortation systems used in industry and the service sector. The following study is concerned with the throughput performance of OA/S-1. The system is assumed to be automated and based on the "loop concept", which is used extensively in industry when throughput (or the number of items sorted per time unit) is relatively large. It is based on a closed-loop conveyor equipped with automated divert mechanisms. A schematic representation of the loop concept is shown in Figure 2, where incoming items are automatically identified and sorted into N sortation lanes using N divert mechanisms. In OA/S-1 a given order may generally be assigned to any lane. The number of lanes is typically less than the number of orders since too many lanes might be required otherwise. Hence, recirculation becomes necessary, since each incoming item may not 3

find an available lane. More importantly, one may consider using the loop for accumulating all the items of an order before the order is assigned to a lane. Another characteristic of OA/S-1 is that, usually, high pick rates are achieved when batch picking is combined with zone picking. That is, pickers fill several orders on each trip they perform within their predesignated pick zones. However, all the items that belong to the same order are not necessarily picked by the same picker. Hence, the OA/S system is required to reestablish order integrity. Furthermore, in order to synchronize the pickers and balance the picking workload, orders are assigned to pick waves (or time windows). The pickers fill only those orders assigned to the current pick wave. No order of the next pick wave is picked before all the picks are completed for the current wave. Pick waves can be as short as 20 minutes and as long as 2 hours, with 1 to 1 1/2 hours representing a typical time window. The objectives of this study are to examine the effects on productivity of the closed-loop conveyor sortation system OA/S-1, of the following factors: a. The number of sortation lanes. b. The distribution of items per order. c. When and how orders are assigned to sortation lanes. d. When the next wave is released into the system. II. LITERATURE REVIEW Bozer and Sharp [4] studied an OA/S similar to the one shown in Figure 2, but focusing on OA/S-2. With OA/S-2, recall that an order either represents a large shipment to, say, a retail store, or it represents part of a shipment containing several orders, that is, the order is part of an order group. In either case, the appropriate shipping door for each order is determined in advance. Hence, with OA/S-2, when a particular item and its order number are identified at the induction point, the control system already knows the appropriate sortation lane assigned to that item. Furthermore, with OA/S-2, typically a sufficient number of sortation lanes are provided so that every incoming item will be destined to a particular lane. Consequently, recirculation is an option to be used only when the corresponding lane is full. Given that each incoming item is destined to one of the sortation lanes, Bozer and Sharp assumed that the total expected rate at which items are removed from the lanes is equal to the rate at which items are processed through the induction point. Using simulation, the authors analyzed the throughput performance of the system as a function of the induction capacity, the number of lanes, the length of the lanes, the presence of a recirculation loop, and the control system. 4

Aside from the Bozer and Sharp [4] study, no published results with general applicability have appeared in the literature. A number of articles that mainly describe the induction point, the tracking (or control) system, the divert mechanisms, and the sortation lanes used in high performance OA/S systems have appeared in trade publications and conference proceedings. Such articles include those presented by Horrey (6], Walsh [10], Suzuki [9], and the Material Handling Institute [12]. A simulation study of an existing OA/S-1 system is reported by Bozer and Mullens [2,3]. In an attempt to improve the performance of the system, the authors study the impact of: introducing the workload in waves (including the criteria to be used to release the next wave), letting orders with single tote bins bypass the loop, using a cross-over to reduce loop length, adding a packing lane, and extending the loop length to allow for more accumulation space. The above alternatives were evaluated only for the existing system with a specific data set. Hence, the results have interesting but limited implications. Nevertheless, according to Bozer and Mullens, extending the loop length actually decreases the throughput capacity of the system while introducing the workload in waves improves it. Unfortunately, existing results on conveyor theory do not apply to OA/S systems. As pointed out by Bozer and Sharp [4], most of the existing models are based on conveyors with discrete carriers. Except for tilt-tray sorters, a majority of highthroughput OA/S systems, however, utilize belt and/or roller conveyors. More importantly, these existing studies assume that the item is removed from the conveyor by the first available unloading station. In OA/S systems, not only is the item assigned or destined to a specific lane but it is diverted automatically; that is, the worker does not have to be available to remove the item from the conveyor. III. ASSUMPTIONS AND SYSTEM OPERATION In the following we will refer to the items being sorted as "totes", although they could just as well be full cases, bagged items, etc. The principal assumptions for the study are listed as follows: 1. The items are picked into totes which are then sorted in pick waves. All the totes that represent an order are assigned to a unique pick wave. A sufficient length of accumulation conveyor is assumed to exist between order picking and the induction conveyor of OA/S-2 such that at least one wave is always ready to be processed. No intermixing of waves is allowed on this accumulation conveyor. 5

2. The pickers operate independently within their pick zones and all the totes are merged ahead of the OA/S system. Consequently, within each wave, tote locations for a given order are randomly distributed. Hence, a given tote is equally likely to be positioned towards the front or the back of a wave. 3. No totes from the subsequent wave are allowed to enter the loop until all the totes of the current wave have been "processed." This assumption is relaxed later, when the waves are allowed to overlap. 4. The number of orders in each wave and the corresponding number of totes for each order are known in advance. Such information is normally required to form the pick waves. However, as described later, it is subsequently used during sortation. 5. The packing rate and the length of the sortation (packing) lanes are assumed to be sufficiently large so that a "full lane" condition does not occur. In other words, it is assumed that the packing operation itself is not a bottleneck. 6. Exceptions such as incomplete orders due to missing totes or containers with non-readable codes are not treated in the model. Such exceptions do occur in real-life, and the control system as well as the OA/S system should be designed to handle them in an efficient, non-disruptive manner. However, provided-that the entire operation is designed and managed properly, such exceptions should account for less than 1% of the totes, and they should not significantly affect the expected performance. Referring to Figure 2, the operation of the system may be described as follows. Totes enter the loop through the inductior conveyor and are identified by scanner 1, which is used for counting the number of totes observed for each order in the wave, Recirculating totes have priority over those totes entering -the loop. Subsequently, the totes travel through four sections of the conveyor loop, numbered one through four. Accumulation conveyor is used in sections 1, 2, and 4, which operates at 60 fpm (18 m/min). No accumulation is allowed in section 3, which operates at 100 fpm (30.5 m/min). Hence, if section 4 is full, the totes accumulate in section 2. Likewise, if section 2 is full, the totes accumulate in section 1, and so on. The minimum wave size is set equal to 120 totes with a maximum possible value of 132. Sections 1 and 2 are assumed to have the capacity to hold 50 and 30, totes, respectively, while section 4 is assumed to hold 18. Thus, excluding section 3, the loop is long enough to accommodate 98 totes or approximately 80% of a wave. Note that some totes will be diverted on their first pass by scanner 2. 6

According to Bozer and Mullens [3], a short loop is likely to cause congestion while longer loops reduce the performance capacity of the system. The above length was determined as a result of preliminary simulations. Needless to say, the performance of the system may be further improved by changing the loop length. Obtaining the optimum loop length is beyond the scope of this study, which is primarily concerned with alternative operating strategies. The loop length can also be expressed in travel time if the tote length is given. A 2 foot (61 cm) long tote box, which was used for this study, would require 100, 60, and 36 seconds to travel through sections 1, 2, and 4, respectively. Section 3 is assumed to be 175 feet (53 m), or 105 seconds, long. Using a 7 foot (2.1 m) center-to-center distance between lanes and allowing 35 feet (10.7 m) to account for the distance from scanner 2 to the first lane plus the distance from the last lane to section 4, section 3 is long enough to serve 20 lanes. Hence, the loop is approximately 370 feet (113 m), or 300 seconds, long. In comparing alternative strategies, the length of section 3 is kept constant at 175 feet (53 m), regardless of the number of lanes; the purpose of this is to isolate the effect of the number of lanes from the effect of the loop length. Each tote entering section 3 is identified by scanner 2. An appropriate clearance is also introduced at this point by inserting a 3 second time gap between consecutive totes. (The minimum space required between two consecutive totes is generally a function of the conveyor speed and the operating speed of the divert mechanisms.) A tote will be diverted only if a sortation lane has been assigned to its corresponding order number. Only one lane can be assigned to an order and vice versa. However, an occupied lane is made available as soon as the last tote of the order currently assigned to it is identified by scanner 2. Note that any tote which belongs to an order with no currently assigned lane must be recirculated. Although the above configuration and assumptions may seem quite specialized, most real-life OA/S systems based on the loop concept are implemented in a similar fashion. Whether or not the exact values used for tote dimensions, conveyor speeds, and time gaps affect the relative ranking of control strategies is beyond the scope of this study. Last, the performance of the system is measured by throughput, the rate at which totes are diverted into the sortation lanes. It is expressed as a ratio obtained by dividing the observed hourly throughput by the maximum induction input. If scanner 2 is 100% utilized and no tote is forced to recirculate, then the system would scan and divert 1200 totes per hour (due to the 3 second time gap inserted at scanner 2). Hence, the throughput ratio is obtained by dividing the observed hourly throughput by 1200. 7

IV. SIMULATION MODEL, INPUT DATA, AND BASE RUN The simulation model consists of standard SLAM and user written subroutines [7]. In addition to the INTLC (input) and OTPUT (output) routines, a total of seven event routines and two special purpose routines were developed for the program. Of major interest in the study are the effect on throughput of the following factors: a. The number of sortation lanes. b. The wave profile, or the distribution of totes per order in a pick wave. c. The lane assignment strategy, or the method for deciding when and which orders should be assigned to sortation lanes. d. The wave release strategy, or the method for deciding when to release the next pick wave from the induction conveyor onto the loop. Wave Profile Four types of distributions are considered for the wave profile, as shown in Figure 3. These distributions were selected because they appear to represent most wave profiles encountered in practice and they offer a broad variety for analysis purposes. Each wave was generated by sampling orders one at-a-time until the wave size exceeded 119. For distributions B and C two-stage sampling was used, as explained below. For each distribution seven waves were generated and stored in a database. To minimize the impact of random variations, the same set of seven waves were used for each alternative situation examined. Referring to Figure 3, distribution A assumes that the number of totes per order is Uniformly distributed between 2 and 12, with a mean of 7.0. It generates, on the average, 17.7 orders for an average wave size of 123.8. Note that orders with single totes are never generated since they are assumed to bypass the OA/S system. Distribution B is identical to A except for the inclusion of a single "large order" which has, on the average, 35 totes. Such a large order typically represents a shipment made to another warehouse or bulk buyer. The maximum wave size is still limited to 132 totes. Distribution B generates, on the average, 13.7 orders for an average wave size of 123.7. The average order size is 9.0 totes. In a two-stage sampling scheme, the large order is generated first. Distribution C also assumes a mixture of two types of order 8

sizes. The first type is Uniformly distributed between 2 and 4 totes while the second type is Uniformly distributed between 14 and 18. In a two-stage scheme, 5 large orders are generated first; then small orders are generated until the wave size exceeds 119. This leads to a situation where, on the average, nearly 25% of the orders represent 70% of the totes. With an average wave size of 121.1 and 18.7 orders/wave, the mean order size is 6.5 totes, slightly less than that of distribution A. Last, based on its near-triangular shape, distribution D generates a relatively large number of small orders. Hence, for a fixed number of lanes, it represents the heaviest sortation workload compared to the other three distributions. Using distribution D, approximately 90% of the orders represent 76% of the totes. The average statistics are wave size of 122.4, 25.9 orders, and 4.7 totes/order. Lane Assignment Strategy An important strategy in lane assignment is that of waiting until all the totes of an order are on the loop, as verified by scanner 1, before the order is "eligible" for assignment to a sortation lane. This strategy is called "order completion enforced." It is used in the base simulation run. A practical advantage of this approach is that orders with missing totes will not occupy sortation lanes. Instead, when the last tote of a wave is scanned, any incomplete orders may be assigned and diverted into a special lane for further action. However, the main idea behind this strategy is that by assigning lanes only to currently complete orders, a lane is not unnecessarily occupied by an order that may have its last tote positioned close to the back of the wave. Recall that we often have more orders than lanes. Obviously, one may also argue that some of the lanes will be idle while awaiting order completion. (A lane is idle if no order is assigned to it.) If the above requirement is relaxed, on the other hand, lanes could be assigned to orders at any point in time. One strategy is to define an order as "eligible" for assignment to a lane as soon as the first tote enters the loop. This strategy is called "order completion relaxed." Another strategy represents a more extreme case: all orders are "eligible" as soon as final information on the positions of all totes in the wave is available. This strategy leads to "advance priority ranking", discussed in Section V. A simple approach to lane assignment is to scan each tote at scanner 2 and check if it belongs to an "eligible" order. If it does, and if a lane is unassigned, the lane is assigned to that order. This approach is called "logic 1 - incidental assignment." 9

This approach may result in the situation where an order remains eligible for an extended time without being assigned, because whenever a tote of that order passes scanner 2, all lanes are momentarily assigned. In the meantime, when a lane does become available, it is assigned to another order whose tote happens to pass scanner 2 at the appropriate moment. "Logic 1 - incidental assignment" can be combined with either "order completion enforced" or "order completion relaxed", resulting in two distinct logics, as shown in Table 1. A more sophisticated approach is to place the "eligible" orders in a logical queue while the corresponding totes recirculate. Hence, when the queue is not empty, one must specify the order to be assigned to the next sortation lane that becomes available. The following logics are tested (see Table 1): Logic 2 - oldest order. Logic 3 - largest order, in number of totes. Logic 4 - smallest order, in number of totes. During the startup period, or whenever the logical queue becomes empty, logics 2, 3, and 4 don't apply, and assignment is based on logic 1. Wave Release Strategy Last, consider the wave release strategy. One alternative is to have non-overlapping waves. That is, the first tote of the next wave is not released until the last tote of the current wave is verified by scanner 2. Such a strategy is quite conservative, and hence it will be used in the base simulation run for comparison purposes. Another strategy is to release the next wave when a predetermined percentage of the totes (or orders) from the current wave have been diverted into the sortation lanes. Such an approach will generally reduce the total idle time for the lanes from one wave to the next. However, prematurely releasing the next pick wave may cause congestion on the loop. Hence, the impact of overlapping consecutive waves and the extent to which they should be overlapped will also be examined. In the base run - which is used as a benchmark for comparing the impact of alternative operating strategies - it is assumed that order completion is enforced and consecutive waves are not overlapped. All four types of wave profiles as well as the four lane assignment strategies (logic 1 through 4) are considered in the base run. 10

V. SIMULATION RESULTS Base Run: Order Completion Enforced, No Wave Overlapping The base run results showing the throughput ratio averaged over seven waves are presented in Figure 4 for distributions A, B, C, and D. For each distribution the average throughput ratio achieved for a given lane assignment logic is shown as a function of the number of sortation lanes. (Recall that the throughput ratio is obtained by dividing the observed throughput by the maximum possible throughput given as 1200 containers per hour). The following empirical observations can be seen in Figure 4: 1. Logic 1 - incidental assignment, consistently yields the highest throughput ratio for all four distributions. However, if sufficient lanes are provided, the differences observed tend to diminish. See, for example, distributions B and C with 16 or more lanes. Note that increasing the number of lanes reduces competition among complete orders for lanes. Hence, the logical queue of complete orders waiting for lane assignment is relatively short, and the assignment logic has little influence in system behavior. 2. For a given number of lanes, a given logic, and a fixed wave size, throughput tends to be inversely related to the number of orders. The highest throughput is observed for Distribution B (13.7 orders/wave), the lowest for Distribution D (25.9 orders/wave), with A and C (17.7 and 18.7 orders) between these two extremes. A large number of orders tends to cause congestion on the loop, as many eligible orders await lane assignment. There do not appear to be- any linear relationships among the important parameters and variables of interest. For example, Distribution D, on the average, contains 46% more orders per wave than A, but takes only 20% longer to process. 3. Changing the distribution of orders/wave while keeping other factors constant, such as the mean number of orders/wave, does not appear to produce a significant change in throughput. Comparing A and C (17.7 and 18.7 orders/wave), Figure 4 shows a slight, but insignificant, advantage for C. 4. Even with 20 lanes, all the distributions yield an average throughput ratio close to 0.70. That is, the throughput achieved is only 70% of the maximum induction input. Even if approximately one lane is provided for each order. Such a low capacity utilization is a result of two factors. First, due to the complete order requirement, some lanes remain idle during the early stages of wave processing. Observe that there is no incentive to enforce this requirement if a sufficient number of lanes exist. Second, since the waves do not 11

overlap, an increasing number of lanes become idle towards the latter stages. Also, as more totes are diverted, the remaining totes on the loop become increasingly sparse. Hence, the time required to divert the last few totes contributes to the low throughput. Order Completion Relaxed, No Wave Overlapping The next set of runs were made with order completion relaxed. Here an order becomes eligible when its first tote is verified by scanner 2. The results showing the throughput ratio averaged over seven waves are presented in Figure 5 for the same four distributions. 5. Logic 1 - incidental assignment, again yields the highest throughput ratios for all four distributions. Again, performance curves of the different logics tend to coincide as the number of lanes approaches the average number of orders. 6. For a given number of lanes and a fixed wave size, throughput again is inversely related to the number of orders, as shown for logic 1 in Figure 6. 7. Relaxing order completion appears to yield significant improvements in throughput only if the number of sortation lanes equals or exceeds the average number of orders/wave. This can be seen in Figure 7 for distributions A, B, and C (see the curves marked by a square and by a plus sign, respectively). For distribution D the results are inconclusive since the average of 25.9 orders/wave exceeds 20, the largest number of lanes examined. When completion is relaxed, an order may occupy a lane for an extended period. On the other hand, if it is enforced, some idle time will incur for-the lanes while waiting for scanner 1 to identify complete orders. Hence, there is no incentive to enforce completion if a sufficient number of lanes are provided. On the other hand, as indicated by the results presented in Figure 7, including those shown for distribution D, if there is contention for lanes, neither strategy appears to outperform the other. Order Completion Relaxed, Wave Overlapping Allowed All the above results are based on non-overlapping waves. As shown in Figure 7, except for distribution B, even with 20 lanes the throughput ratio is still approximately 0.80 to 0.85 for A and C, and less than 0.70 for D. As discussed earlier, some lane idle time occurs towards the latter stages of wave processing before the next wave is released. Hence, the next set of simulation runs were aimed at increasing the throughput ratio by reducing lane idle time between consecutive waves. This can be accomplished by releasing the next wave so that some totes of the next wave are already on 12

the loop before all the totes of the current wave have been diverted. Logic 1 - incidental assignment was used to control lane assignment. 8. Releasing the next wave when 90% of the orders in the current wave have been assigned to a sortation lane, results in a throughput improvement ranging from 5 to 25%. These results are shown in Figure 7 (by the curves marked by a diamond). With 20 lanes the throughput ratio either exceeds or approaches 0.90. The 10% overlap was obtained through experimental runs for each distribution; interestingly, 10% yielded the best results in every case. Advance Priority Ranking of Orders, Wave Overlapping Allowed Another potential avenue to explore is based on priority ranking the orders in advance. That is, if a scanner is placed up-stream where each wave is accumulated, one can identify each tote and its relative position within the wave before the wave is released. This information can be subsequently used to rank all the orders within a wave in terms of the priority they have in obtaining a sortation lane. The above concept was implemented with a heuristic procedure based on the position of the last tote of each order. The order with its last tote closest to the front of the wave is assigned the highest priority. In this respect the heuristic resembles the "shortest processing time" (SPT) approach used in scheduling. To retain flexibility the orders are not assigned to specific lanes, but rather priority ranked, where a 1 represents the highest priority. As specific lanes become available, they are reserved for unassigned orders, based on the priority ranking. During the early stages of wave processing more than one lane may be available. Suppose two lanes are available at some instant in time, and that the lowest priority among all the orders currently assigned is 4. Hence, the system is ready to assign the order with priority 5. However, since two lanes are available, the system accepts orders with priority 5 or 6, whichever is detected by scanner 2 first. Wave overlapping is automatically controlled, by assigning higher priority rankings to all orders in the current wave then to any order in the next wave. 9. Priority ranking the orders in advance did not improve the throughput ratio, at least for the two distributions for which it was attempted, A and D. The results are shown in Figure 7 (by the curves marked by a diamond). In fact, one may argue that it leads to a decrease in throughput. The disappointing performance of the heuristic can be attributed to two reasons. For one, the priority ranking of orders based on the last tote of each order on the accumulation conveyor tends to become meaningless after these orders have been forced to recirculate on the loop. When a lane becomes 13

available, based on the SPT rule the order that should receive the highest priority is the one with its last tote closest to scanner 2; except that now we would like to define the last tote as the one furthest from scanner 2, beginning at scanner 2 and going counterclockwise (see Figure 2). Recirculation obviously can cause a different tote to be the last one. The second reason is the fact that the procedure ignores the first tote of each order. This is perhaps best demonstrated by a small example. Consider a case where 10 orders are ranked (from highest to lowest) as follows: 4, 9, 6, 3, 8, 7, 1, 2, 5, and 10. Further, suppose that only four lanes (labeled L1, L2, L3, and L4) are provided. Table 2 presents the results of the example. First, an explanation of the columns in the table is in order: Column B: Time of observation at scanner 2. C: Order number of tote at scanner 2. D: Number of totes is that order (known in advance). E: Wave number (all belong to wave #1). F: Priority ranking of that order. G-J: Priority rankings of orders assigned to lanes 14. Filled-in zero means no order is currently assigned to lane. K: Decision to divert tote at scanner 2. L: Assigned lane number for tote at scanner 2. Beginning at time 166, a tote of order #3 is observed at scanner 2. Since order #3 has priority ranking 4 and all lanes are free, an assignment is made, to lane 1, and the tote is diverted. Similarly, at time 169 an assignment to lane 2 is made when a tote of order #9, with ranking 2, is observed at scanner 2. At time 175 the first tote of order #2 is not assigned sinced the order has a ranking of 8; the two free lanes are reserved for orders 4 and 6, with rankings of 3 and 4, respectively. In fact, waiting for the first tote of order #6 causes lane 4 to be idle until time 241. But note that the first tote of order #6 arrives after the last tote of order #4 (see column I for lane 3). Hence, lane 4 was unnecessarily reserved for order #6. Attempts to overcome this weaknesses were not successful mainly because the problem is complicated due to recirculating totes and overlapping waves. However, an interesting analogy can be constructed for a single wave if the totes are required to be diverted into the lanes in the order in which they accumulate up-stream before the wave is released. That is, the first and last totes of an order diverted into a lane are the first and last totes on the accumulation conveyor before the wave was released. For the above case, each order can be visualized as a piece of tape wrapped around a rotating cylinder. Each lane can be 14

visualized as a peeling device. The objective is to peel all the pieces in minimum rotation time. An example with five orders and two lanes is shown in Figure 8. (A dynamic version of the problem with multiple waves can be visualized if separate devices were used to apply the tapes onto the cylinder). The above problem is analogous to Automated Guided Vehicles (AGV's) circulating in a single, closed-loop path. Each piece of tape represents one trip and each peeling device represents an AGV. The two extreme points of each piece mark the pick-up and drop-off points for the corresponding trip. For the above AGV system, Bartholdi and Platzman [1] have shown that the required number of vehicle trips around the loop can be nearly-minimized by using the First-Encountered-First-Served (FEFS) rule. As noted by the authors, an analogous strategy exists for retrieving information from computer drums. (See Fuller [5] and Stone and Fuller [8]). The FEFS rule is analogous to logic 1 - incidental assignment. Hence, if a static, single wave version of the OA/S problem is considered and the totes are required to be diverted in the sequence in which they initially appear in the wave, then logic 1 will nearly minimize the time required to divert them all. Once the totes begin recirculating, the totes in each order can still be viewed as strips of tape on the cylinder, except that the strips change from time to time. At any one instant we can still view the problem as being equivalent to an AGV problem on a single, closed-loop path. Hence, logic 1 should be expected to perform well. The above analogy simply reinforces the conclusions drawn from the empirical evidence. Unless one has the capability to track tote locations around the loop at all times, it is doubtful that a heuristic procedure that consistently outperforms logic 1 can be- developed. VI. CONCLUSIONS Four types of distributions of totes per order were considered for an automated OA/S system with multiple lanes. Alternative lane assignment strategies and wave release strategies were evaluated for each distribution from a throughput standpoint, using a SLAM simulation model. The following conclusions can be drawn from the results: Logic 1 - incidental assignment, consistently yields the highest throughput ratio. If the number of sortation lanes equals or exceeds the average number of orders per wave, the advantage of logic 1 over logic 2 - oldest order, logic 3 - largest order, and logic 4 - smallest order, tends to diminish. It is notable that logic 1 is the simplest procedure to implement. 15

For a given number of lanes, a given logic, and a fixed wave size, throughput tends to be inversely related to the number of orders. If the average number of orders per wave exceeds the number of sortation lanes, requiring all totes of an order to be on the loop vetsus only the first tote of the order, resulted in no apparent advantage. However, if the average number of orders is less than or equal to the number of lanes, then relaxing the order completion requirement does improve throughput. A considerable improvement (5-25%) in throughput can be obtained by reducing lane idle time between consecutive waves. Overlapping the waves by releasing the next wave when 90% or more of the orders in the current wave have been assigned to a lane, appears to provide an appropriate overlap for the system examined in this study. Priority ranking of the orders in advance, before releasing the wave onto the loop, did not improve the throughput ratio over the combination strategy of logic 1 - incidental assignment, order completion relaxed, and wave overlapping allowed. Unless one can track tote locations around the loop at all times, it is doubtful that a heuristic procedure that consistently outperforms logic 1 can be developed. VII. ACKNOWLEDGEMENTS This study was partially supported by the National Science Foundation, Grant CDR-8300965, and by the Material Handling Research Center. The authors would like to thank Dr. Leon F. McGinnis for the rotating cylinder analogy to the firstencountered-first-served rule. 16

BIBLIOGRAPHY 1. Bartholdi, J. J., III and Platzman, L. K., "Decentralized Control of a Fixed Route Automatic Guided Vehicle System," TR-8505, Material Handling Research Center, Georgia Institute of Technology, Atlanta, Georgia, February 1985. 2. Bozer, Y. A., "Simulation Modeling in Warehousing and Physical Distribution Systems," 33rd Annual Material Handling Management Course, Airlie, Virginia, June 1986. 3. Bozer, Y. A. and Mullens, M. A., "Designing an Automated Sortation System Using Simulation," Joint ORSA/TIMS National Conf., Orlando, Florida, 1983. 4. Bozer, Y. A. and Sharp, G. P., "An Empirical Evaluation of a General Purpose Automated Order Accumulation and Sortation System Used in Batch Picking," Material Flow, Vol. 2, No. 2, 1985, pp. 111-131. 5. Fuller, S. H., "An Optimal Drum Scheduling Algorithm," IEEE Trans. Comp. C-21, Vol. 77, 1972, pp. 1153-1165. 6. Horrey, R. J., "Sortation Systems: From Push to High-Speed Fully Automated Applications," Proc. 5th Intl. Conf. on Automation in Warehousing (ICAW), Atlanta, GA, Dec. 1983, pp. 7783. 7. Pritsker, A. A. B., "Introduction to Simulation and SLAM," 2nd Ed., Wiley, 1984. 8. Stone, H. S. and Fuller, S. H., "On the Near-Optimality of the Shortest-Latency-Time-First Drum Scheduling Discipline," Comm. ACM, Vol. 16, No. 6, 1973, pp. 352-3. 9. Suzuki, J., "The Application and Suggestion of Sorting Machine in Japan," Proc. 4th Intl. Conf. on Automation in Warehousing (ICAW), Tokyo, Sept. 30 - Oct. 2, 1981, pp. S6-3-1 to S6-3-39. 10. Walsh, P., "Carton Sortation in the Distribution WH," Proc. 3rd Intl. Conf. on Automation in Warehousing (ICAW), Chicago, Nov. 1979, pp. 15-28. 11. Wilson, H. and DeMaria, T., "An Evaluation of Alternative Techniques for Order Fulfillment," Annual NCPDM (previously Council of Logistics Managament) Meeting, New Orleans, Louisiana, Vol. 2, October 1983, pp. 627-644. 12. Considerations for Planning Sortation in Conveyor Systems, The Material Handling Institute, Conveyor Section, 3/82-10M, 1982. 17

ORDERS * RECEIVING UNLOADING Y-M ORDER PICKING * * FULL-CASE PICKING SPLIT-CASE PICKING OA/S-1 PACKING _ r OA/S-2 PALLETIZING - SHIPPING * i m i.. * * * * * I Figure 1. Example Containing Both OA/S-1 and OA/S-2.

I NOUCIION CONVIVON 1l SI fiON 1 s c,oo 4 s *cooN 2 divert mechanism stC lON 3 SCA NNI A 2 v V -0 —-SO IAIION ANIS Figure 2. Schematic Representation of OA/S-1

* I t T I UOl N A * 1 I t II PI$T#IUTION a (two-stage sampling) -- I I 2 3 4 S O 10 I TOfTS OISTIaOUTION c (two-stage sampling) I Vr.41.3-.2..-a.3 I 30 31 32 33 34 3S 34 37 31 39 40 TOT IS Io - - TO TO0IS 14 IS 16 17 1I TO IS ISTlIIUTION 0 2 3 4 S ~ 7 tI 10 11' TOT S Figure 3. Distributions Used for Generating Wave Profiles.

Table 1. Lane Assignment Logics Logic Order Completion Enforced Order Completion Relaxed 1. Incidental assignment 2. Oldest order 3. Largest order 4. Smallest order Next tote (of a complete order) detected at Scanner 2. Oldest (complete) order (in logical queue) first.* Largest (complete) order (in logical queue) first.* Smallest (complete) order (in logical queue) first.* Next tote detected at Scanner 2. Oldest order (in logical queue) first.** Largest order (in logical queue) first.** Smallest order (in logical queue) first.** *Order completion time marked by scanner 1, based on last tote of order. **Order arrival time marked by scanner 2, based on first tote of order.

1.00 0.90 0 N4 to,.. 0 O 3 ro E&o 0.80 0.70 0.60 0.50 0.40 - 0.30 -- 8 0 LOGIC I 10 12 14 16 18 20 A LOGIC 4 NUMBER OF LANES + LOGIC 2 o LOGIC 3 Figure 4. Throughput Ratio versus the Number of Sortation LanesBase Run: Order Completion Enforced, No Wave Overlappinv

1.00 0.90 0 M 4 0 Cd E-4 0.80 0.70 0.60 0.50 0.40 - 0.30 8 o LOGIC 1 10 12 14 16 18 20 NUMBER OP LANES o LOGIC 3 + LOGIC 2 A LOGIC 4 Figure 4. (Cont'd)

1.00 0.90 0 bd 14 II 0::E 0 we 0.80 0.70 0.60 0.50 0.40 0.30 - 8 0 LOGIC I 10 12 14 16 18 20 A LOGIC 4 NUMBER OF LANES + LOGIC 2 o LOGIC 3 Figure 4. (Cont'd)

1.00 0.90 0 M n, 4 lg 0 to Oi [. 0.80 0.70 0.60 0.50 0.40 - 0.30 - 8 o LOGIC 1 10 12 14 16 18 + LOGIC 2 NUMBER OF LANES o LOGIC 3 A 20 LOGIC 4 Figure 4. (Cont'd)

(p,,uo3) *' a.n6Lj CZ I I. *I t I I I I t llll~, m ll 1t,1, 1 1 1 I! ^ ^ ~~~~~~~~~~~~~ Li" y 3w o m a 1 i.*9 - f I UI "I i Wl. 3 I I IT 51n a s a *1 it t It f* t o I1 S o 3M - t 3I 9 cum1 a 0 I 7 It tI t1 II It i!! i i i i i! i Iu T3B1 0 an o I Sr m * n,1. o I S..on a, I wea wea t3 l * * t13 o i jo a It I tI t l IX It I

1.00 0.90 0 4 0 E 0.80 0.70 0.60 0.50 0.40 - 0.30 - 8 al LOGIC I 10 12 14 16 18 20 + LOGIC 2 NUMBER OF LANES o LOGIC 3 LOGIC 4 Figure 5. Throughput Ratio versus the Number of Sortation Lanes - Order Completion Relaxed, No Wave Overlapping

1.00 0.90 0 I o 0 0 0.80 0.70 0.60 0.50 0.40 - 0.308 0 LOGIC 1I 10 12 14 16 18 20 NUMBER OF LANES o LOGIC 3 + LOGIC 2 LOGIC 4 Figure 5. (Cont'd)

1.00 0.90 0 tQ 3 I. 0 3 O c. 0.80 0.70 0.80 0.50 0.40 - 0.308 0 LOGIC I 10 12 14 186 18 20 A LOGIC 4 NUMBER OF LANES o LOGIC 3 + LOGIC 2 Figure 5. (Cont'd)

1.00 0.90 0 I. At 0 at E" 0.80 0.70 0.60 0.60 0.40 - 0.30 8 o LOGIC I 10 12 14 1 18 NUMB Of LANES o LOGIC 3 A 20 LOGIC 4 + LOGIC 2 Figure 5. (Cont'd)

A B, LU LU i S& d i La *.. I*, 1 1, I iW * W W II la 14 i to a is is 14 to BAm W tLou w up LU n 1 em I ~ 3 4 oLI L LU A4 * 0L, LAo- La IM * U i 1 n4. u * eA * LeO * LI S I, — 14 16 15 U 5 16 13 14 15 iS o LICL * GIC ~ LG ~ ~ o I~ r 1Ca 1 * *, JC3 ~ * C' a~~~~~ ~~~~~~~~~~~~~ diei ~ ~ccI "1 Sc ~ uc ~t ~ > Figure 5. (Cont'd)

1.00 0.90 0.80 0 te 4 0.70 A. 0 0.60 0 0.50 0.50 0.40 0.30 8 10. 12 14 16 18 20 NUMBER OF LANES Distribution A B -== 0 Orders/Wave 17.7 13.7 18.7 25.9 Figure 6. Relation of Throughput Ratio to Number of Orders/Wave and the Number of Sortation Lanes - Logic 1 - Incidental Assignment, Order Completion Relaxed, No Wave Overlapping.

1.00 0 I'. to 0 0 O PS 0.90 0.80 0.70 0.60 0.50 0.40 0.30 8 10 12 14 16 18 20 NUMBU OF IANES 0 Order completion enforced, no wave overlapping, logic 1. * Order completion relaxed, no wave overlapping, logic 1. ~ Order completion relaxed, wave overlapping allowed, logic 1. a Wave overlapping allowed, advance priority ranking. Figure 7. Relation of Throughput Ratio to Strategies and Number of Sortation Lanes.

1.00 0.90- 0.80 - 2 0.70 - 3 0.60- 0 0.50 0.40 - DI< 13, 9.( 0.30 - 8 10 12 14 16 NUMBER OF LANES O Order completion enforced, no wave overlapping, logic 1. * Order completion relaxed, no wave overlapping, logic 1. * Order completion relaxed, wave overlapping allowed, logic 1. ~ Wave overlapping allowed, advance priority ranking. 18 20 Figure 7. (Cont'd)

1.00 0.900 0.80 - C~ 0,70 5 0.60~ot 0.50 0.40 DIS1 18.7 6.5 0.30-,,,. I i,. 8 10 12 14 16 NUMBELB O? LINES o Order completion enforced, no wave overlapping, logic 1. + Order completion relaxed, no wave overlapping, logic 1. 0 Order completion relaxed, wave overlapping allowed, logic 1. & Wave overlapping allowed, advance priority ranking. 18 20 Figure 7. (Cont'd)

1.00 - 0 0.80 3 0.60 0.50 0.40 i DISTRIBUTION D 25.9 ORDERS/WAVE 4.7 TOTES/ORDER 0.30': l-l I i I I' l 8 10 12 14 16 18 20 NUMBEB OF LAN1S O Order completion enforced, no wave overlapping, logic 1. + Order completion relaxed, no wave overlapping, logic 1. * Order completion relaxed, wave overlapping allowed, logic 1. a Wave overlapping allowed, advance priority ranking. Figure 7, (Cont'd)

i 0 a 0 0 6 p a I I I1 14 wrum l I 1s Ia 14 IIMIIB f IW I~ 16 to S p a I, a 0 I a, 14 ~Ir It I U I 1i Is 14 |~~ N@a. s ii a O Order completion enforced, + Order completion relaxed, r o Order completion relaxed, o A Wave overlapping allowed, a no wave overlapping, logic 1. no wave overlapping, logic 1. wave overlappirn allowed, logic 1. advance priority ranking. Figure 7. (Cont'd)

1 2 3 4 5 IPP Figure 8. The Rotating Cylinder Analogy to the First-EncounteredFirst-Served Rule

Table 2. Example of Lane Assignment Using Advance Priority Ranking A B C D E F G H I J PRIORITY RANKING OF ORDER ASSIGNED TO K TIME OF ASSIGNED OBSERV. LANE # AT FOR TOTE SCANNER 2 1. 166.00 2. 169.00 2. 172.00 0. 175.00 1. 178.00 0. 181.00 0. 184.00 0. 187.00 2. 190.00 3. 193.00 0. 196.00 0. 199.00 0. 202.00 0. 205.00 3. 208.00 2. 211.00 0. 214.00 3. 217.00 1. 220.00 0. 223.00 0. 226.00 1. 229.00 0. 232.00 3. 235.00 3. 238.00 4. 241.00 2. 244.00 2. 247.00 3. 250.00 0. 253.00 1. 256.00 1. 259.00 4. 262.00 1. 265.00 2. 268.00 1. 271.00 1. 274.00 3. 277.00 0. 280.00 4. 283.00 ORDER # OF TOTE TOTES AT IN SCANNER 2 ORDER 6. (J> ~6. 6. 2. 7. ( a6. 2. 7. 7. 2. 5. 5. 6. 3. 5. 5. 1. 2. 10. 4. 10. 4. ~A ~~3. i SJ6. 7. 3. 6. 5. 5. 2. 7. 3. 3..7 2. 6. 6. ~s {3. 10. 4. 6. 6. 8. 2. 2. 7. 7. 2. 2. 7. 2. 7. 5. 5. 10. 4. 1. 2. PRIORITY RANKING WAVE # OF ORDER 1. 4. 1. 2. 1. 2. 1. 8. 1. 4. 1. 8. 1. 6. 1.. 9. 1. 2. 1. 1. 1. 9. 1. 7. 1. 10. 1. 10. 1. 1. 1. 2. 1. 8. 1. 1. 1. 4. 1. 9. 1. 8. 1. 4. 1. 9. 1. 3. 1. 3. 1. 5. 1. 2. 1. 2. 1. 3. 1. 10. 1. 4. 1. 4. 1. 5. 1. 8. 1. 6. 1. 8. 1. 8. 1. 9. 1. 10. 1. 7. LANE L1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 8 8 8 8 8 8 a L2 L3 * S 2 S 2 S 2 S 2 S 2 S 2 I 2 5 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 0 2 S 2 0 2 0 2 S 2 3 2 3 2 3 2 3 2 3 * 3 6 0 6 0 6 I * * * 0 6 I 6 0 6 0 6 9 6 9 6 9 L4 I S S S S S S S S 0 I S I S S S S 0 S S S 5 5 5 5 5 5 0 0 S 0 7 DIVERT? YES YES YES NO YES NO NO NO YES YES NO NO NO NO YES YES NO YES YES NO NO YES NO YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES NO YES Notes: 1. Priority Ranking of Orders is: 4, 9, 6, 3, 8, 7, 1, 2, 5, and 10 2. e means no order currently assigned to lane. 3. Orders with high priority shown by L 1st priority V 3rd priority D 2nd priority Q 4th priority