Abstract Number: 002-0486
FORMING BATCHES: EXHAUSTIVE VS PARTITIONING METHODS
Second World Conference on POM and 15th Annual POM Conference, Cancun, Mexico, April 30 – May 3, 2004.
Ramakrishnan Sundaram
Martha A. Centeno
Industrial & Systems Engineering
Florida International University
10555 W. Flagler Street, Miami FL 33174 U.S.A.
Abstract
In this paper, we discuss the challenges of forming batches. Forming batches is required in a variety of optimization problems that involve finding optimal sequences or schedules. We have experimented with two approaches: exhaustive and partitioning. Under the exhaustive method, the main challenge was generating all the possible combinations for each batch. Once that was achieved, a ranking method was used to determine the best combination; however, when the number of items to batch is larger than 50 and the batch size is larger than 3, the time required to generate the combinations and to rank them is prohibited. An alternate partitioning method has resulted in a major reduction in computational time and only a minimal reduction on the optimality of the solution.
1.Introduction
Batch forming or grouping is a problem that has persisted in may engineering problems. The objective in any grouping problem is to form best groups of elements, be it customer orders in warehouses, patients in clinics, items in inventory or even selection of a menu for a reception. However, the conception of “best groups” differs from problem to problem. In any case, the groups are formed based on specific criterion or criteria. The criteria basically exploit the similarity between “best groups” of elements and combine them together. Forming groups are always for a purpose and there is always a price paid (cost) for forming groups by combining elements with less similarity. The forming of groups, however, is constrained by either number of allowable groups that can be formed or number of elements allowable within a group for a given set of elements. The latter case can be further classified as:
1)Strict Group Size - Equal number of elements in all the groups (allowable size) except for the last group formed.
2)Flexible Group Size - Any number of elements within the group as long as they are all within the allowable group size.
This paper presents a criterion for grouping elements by Strict Group Size Grouping. The grouping was developed for forming batches of customer orders to be processed in a manual order-picking warehouse. The process of forming batches of customer orders is called order batching. According to a study by Institute of Materials Management, in the U.K in warehouse operations, the cost incurred is mainly in the picking of orders by pickers (Drury, 1988). This depends on the route taken by the pickers while processing the orders. The route eventually depends on the routing policy and on the individual orders present in the batch (order-batching policy). The routing policy is generally traversal i.e. when a picker enters an aisle, he/she completely traverses the aisle, and U-turn is not allowed. We have considered the traversal routing policy in these experiments. The order-batching problem can be defined as how to sequentially assign orders to batches of pick lists such that the picker route interference is minimized. Hence the objective in the order-batching problem is to from batches of orders such that the route to be taken by the pickers to process the batch is very common. In warehouses, pickers move along aisle to pick items from racks. Hence the route can be safely expressed in terms the aisle to traverse. An exhaustive as well as a short-cut (partitioning) method was proposed and analyzed. The methods were implemented as a heuristic in Visual Basic 6.0.
Section 2 provides some previous approaches used in solving order-batching problem. Section 3 gives the nomenclature used in the paper. Section 4 explains the criteria used for forming batches in this effort. Sections 5 and 6 explain the exhaustive and partitioning technique respectively. Section 7 compares the 2 techniques. The last section gives the conclusions based on the comparative analysis.
2. Previous Research in Order Batching
Literature in order batching per se is scarce. Rosenwein (1996) notes that the structure of the order-batching problem is too complex for formulating an objective function in mathematical programming. Hence, ruling out an optimization based solution procedure.
Elsayed and Stern (1983), elaborated order processing as a series of three steps with each step having a set of rules. The three steps are: seed selection (4 rules), Order congruency (3 rules), and addition of orders (2 rules). A seed for any batch is the basic or the first order selected in the batch. They compared the performance of 24 algorithms that resulted from combinations of the rules of each step. They formulated the problem with the objective to reduce the distance traveled over all tours. They combined the orders in terms of common item locations and minimum distance between item locations for automated warehousing systems.
In 1989, Elsayed and Unal developed four order-batching algorithms for automated S/R systems based on timesaving criterion of forming batches. The four algorithms are namely, EQUAL, SL, MAXSAV and CWright algorithms. They also developed a travel-time estimate procedure to calculate the time saved in forming the batches. They assumed that the pick-up and storing time are negligible compared to total travel time.
In 1992, Gibson and Sharp developed order-batching procedures based on the assumption that the location of the items in terms of aisle is known. According to their procedure, of all the available orders, an order in the top of the list is chosen as seed order and successively orders are chosen in the batch based on the “sequential minimum distance” of the orders until the order capacity for a batch reaches a limit. Rosenwein (1996) followed up the work of Gibson and Sharp (1992) in developing and order-batching heuristic for a manual order-picking warehouse. He proposed two alternative distance metrics to measure the travel-distance for the batch of orders. Even though the heuristic took computationally longer that the one Gibson and Sharp developed, it reduced the labor effort for picking by one-third. Ruben and Jacobs (1999) studied the performance of five different order batching strategies and observed that turnover based assignment reduced the distance traveled by pickers in the warehouse, but it resulted in increased traffic in the aisle. Random assignment of items resulted in increased travel time of pickers, but it did not give way to congestion. Family based assignment gave the best results by reducing travel distance of pickers and had the aisle traffic in control. They conducted a sensitivity analysis by increasing the number of pickers and found that the pick rate was affected considerably in turnover-based assignment than in the family based assignment. Further, they recognize the importance of developing computationally efficient methods for determining the family of items from the customer orders.
3.Nomenclature
/ = / Total number of orders to pick/ = / Number of intervals in the delivery time period
/ = / Number of intervals in the picking time period
/ = / Number of orders to be picked in the interval in Picking period
/ = / Number of aisles existing in the warehouse
/ = / Matrix (x 3) of order records,
= 1,2… and
For = 1 Unique identifier for order
For = 2 Order due time interval (1 to NP) for order
For = 3 Number of items to be picked in the order
/ = / Same as but sorted by class
/ = / Binary matrix () of aisles required by all orders
For
/ = / Vector for order-interval assignment
, If order belongs to interval
For
/ = / Vector for order-batch pairing.
For
/ = / Batch size (management policy)
/ = / Number of batches in the th picking interval
/ = / Total number of batches
/ = / Correlation factor for the ith batch of orders
/ = / Binary matrix () of aisles to be traversed for each batch
For
/ = / Set of aisles to be traversed for batch j.
A row of corresponding to batch
/ = / Set of aisles to be traversed for order i.
A row of corresponding to order
/ = / Number of orders to be picked from aisle k for batch
/ = / Number of aisles to be traversed for picking batch
/ = / Number of items to be picked for any batch
/ = / Matrix of Partitions of orders
Partitions (1 to
Total Orders (1 to )
Aisles (1 to )
/ = / Matrix representing presence of order in Partition
Partitions (1 to
Total Orders (1 to )
/ = / Matrix of number of orders in each aisle for a Partition
Partitions (1 to
Aisles (1 to )
/ = / The aisle with maximum in Partition
4.Batching Criteria – Aisle Correlation Factor
Groups are formed based on certain criteria exploiting the similarity between the elements that form the group. In case of order batching, the batches of orders are formed based on commonality of aisles among the orders that form the batch. The aisle commonality is being called Aisle Correlation, whereas the degree of commonality we are calling it Aisle Correlation Factor (ACF).
The objective in forming the batches is that the orders with most common aisles be batched first. Aisle commonality is chosen instead of item commonality as orders with common aisles already consist of common items. The commonality is measured in terms of the correlation among the batch of orders considered. Initial batches have high correlation and correlation progressively diminishes as more and more batches are formed.
Batches are formed for a set of orders to be processed. The total orders to be processed are divided in to smaller subsets to be processed in smaller time intervals[*] based on their delivery due times (this is specified by the customers in the order). Each interval has orders to be processed. Batches are formed for these orders.
It is required that a batch is formed such that a minimum number of aisles is traversed. A way to determine if orders have a minimum number of aisles to traverse (min ) is by computing an aisle correlation factor () for batch . This correlation factor is a measure of the density (overlapping) of the orders in the batch. is a measure of the percentage of orders in the batch that have common aisle. When there are ties in the correlation factor, these ties should be broken arbitrarily. For example, assume that there are 6 aisles, = 2, and there are 4 orders. The aisles to visit () are shown in Table 1. Given this information, there will be 2 batches to be formed, and they can be as shown in Table 2.
Let = proportion of orders in batch that visit aisle
Then, where
Since , then
Table 1: Aisles to be traversed by orders
Order/aisle / 1 / 2 / 3 / 4 / 5 / 61 / 1 / 1 / 1 / 0 / 1 / 0
2 / 0 / 1 / 1 / 1 / 0 / 1
3 / 1 / 0 / 1 / 1 / 1 / 1
4 / 0 / 1 / 0 / 1 / 0 / 1
Table 2: Correlation factor for all 2-way combinations
Batch / Aisle / 1 / 2 / 3 / 4 / 5 / 6 / Q(j) / rho(j)1 / 1 & 2 / 1 / 1 / 1 / 1 / 1 / 1 / 6 / 0.667
/ 0.5 / 1 / 1 / 0.5 / 0.5 / 0.5 / 4
2 / 1 & 3 / 1 / 1 / 1 / 1 / 1 / 1 / 6 / 0.750
/ 1 / 0.5 / 1 / 0.5 / 1 / 0.5 / 4.5
3 / 1 & 4 / 1 / 1 / 1 / 1 / 1 / 1 / 6 / 0.583
/ 0.5 / 1 / 0.5 / 0.5 / 0.5 / 0.5 / 3.5
4 / 2 & 3 / 1 / 1 / 1 / 1 / 1 / 1 / 6 / 0.750
/ 0.5 / 0.5 / 1 / 1 / 0.5 / 1 / 4.5
5 / 2 & 4 / 0 / 1 / 1 / 1 / 0 / 1 / 4 / 0.875
/ 0 / 1 / 0.5 / 1 / 0 / 1 / 3.5
6 / 3 & 4 / 1 / 1 / 1 / 1 / 1 / 1 / 6 / 0.667
/ 0.5 / 0.5 / 0.5 / 1 / 0.5 / 1 / 4
5.Exhaustive Correlated Batching
The best combination is the one with the highest , which in this case is combination (2,4). Thus, batch # 1 order 2 and order 4. The next best are (1,3) and (2,3), which have the same . Breaking ties arbitrarily, combination (1,3) is chosen. This combination is reviewed to ensure that none of the orders in it have already been assigned.
Let, = OrderID= Set of orders in combination j.
= Set of orders in permanent batch k.
= Number of permanent batches chosen so far.
Then, if for all , make a permanent batch.
For the example, the orders in the combination (1,3) are not members of the union of all previous batches; thus, it is made a permanent batch, which brings the total number of permanent batches to two; thus, the heuristic stops. On the other hand, if the tie had been broken so that the combination (2,3) had been chosen, reviewing this combination against the union of all permanent batches would reveal that one of the orders (namely 2) is a member of the union; hence, this is no longer a feasible combination and must be discarded. The next best combination is chosen, leading to (1,3). However, when the number of combinations to be reviewed is a higher value, determining the best combination of batches may not be an easy task. For this, all the combinations are sorted in the descending order according to their ACF. The sorted list is shown in Table 3. Once the sorted list is obtained, the combination with the highest ACF is declared as the first batch. The orders in this batch are assigned in the set if orders assigned to a permanent batch. Then, the combination with the next highest ACF is considered. If any of the orders in the combination is not present in the set of orders that already assigned as a permanent batch, then, declare the combination as the next batch, else consider the next combination. Hence all combinations are explored exhaustively to form best batch of orders.
Table 3: Sorted list of order combinations based on ACF
Combination / Orders / ACF1 / 2 & 4 / 0.875
2 / 1 & 3 / 0.750
3 / 2 & 3 / 0.750
4 / 1 & 2 / 0.667
5 / 3 & 4 / 0.667
6 / 1 & 4 / 0.583
The ECB for forming batches of size from orders consists of the following steps:
- Determine and generate the combinations of the total orders consisting of orders (). Set = 1
- Find for all the combinations.
- Arrange the combinations in descending order according to .
- Choose the combination for which is maximum. If there are ties, break them arbitrarily.
- If any of the orders in the combination were previously assigned to a batch, discard the combination from the sorted list and go to Step 4. Else go to Step 6.
- Declare the combination as batch with aisle set .
- Mark the set of orders that form this batch as “assigned” to prevent them from being considered again.
- If number of unassigned orders in set , declare the remaining orders as the final batch and got to Step 9. Otherwise go to step 4.
- Stop
While experimenting with ECB, we realized how high was the computational time required to form batches and assign batches. The computational time increased exponentially with the number of orders to process. This behavior is attributable to the combinatorial explosion of the problem. The original heuristic (ECB) explores all the combinations of batches to land at the best possible batches. Thus a partitioning approach was later pursued (Section 6). Now, we discuss the characteristics of the computational time issues of ECB for various numbers of orders and orders in an interval. The heuristic was tested on local computer workstation that has an Intel Pentium 4 Processor 2.8 G Hz., 512 MB RAM, with a hard disc space of 40 GB. The scenario considered for testing the batches were based on the principle that orders were processed in different intervals. The total orders refer to the summation of orders in all these intervals. Here we consider orders with 8 intervals.
Figure 1 clearly shows the exponential explosion of required computational time, even with a number of orders as low as 300. On a normal day, a manual order picking warehouse serving groceries receives anywhere between 2000 and 3000 orders which will require more than a day to get the solution. The observed run time shown in Figure 1 is for batch size of 3 orders. With the change in batch size, the number of possible batch combinations changes. The behavior of the run time with increase in number of orders in an interval for batch size 3 is shown in Figure 2. Generalizing, the behavior of run time for increase in of combinations due to increase in either order size or batch size is shown in Figure 3.
Figure 1: Run Time Characteristics for total orders
Figure 2: Run time at different order sizes
Figure 3: Run time at different number of combinations
6.Partitioning Correlated Batching (PCB)
This approach is based on the idea of grouping or partitioning the orders according to the density of the aisles. When the number of orders in the partition small enough, a batch is formed; otherwise, the promising orders are further partitioned. Recall that the correlation factor among a batch is calculated based on the order density for all the aisles in the facility. Orders are partitioned based on order density of one aisle at a time. Forming batches using this approach requires two steps:
1)Forming partitions
2)Forming batches
The first procedure is done one or more times while forming each batch in a given set of orders.
In order to explain the partitioning approach, assume that there are 6 aisles, = 2, and there are 4 orders. Given this information, there will be 2 batches to be formed; the number of possible combinations of batches is 6. The given set of matrix (Table 4) is considered as Partition 1. For each of those aisles, the order density is calculated, and the aisles with maximum density are identified. In this example, Aisles 2, 3, 4 and 6 have maximum of 3 orders (Table 5). When finding the aisle density, it must be checked if the number of orders is greater than or equal to the batch size. If no, we are ready to form batches as explained later. If yes, then select an aisle arbitrarily among the aisles with maximum density. For example, let us choose aisle 2. Now extract the orders that require traversing aisle 2: orders 1, 2 and 4. These orders will now form Partition 2 as shown in table Table 6. For the computer implementation of this approach, it is necessary to keep Order 3, but Order 3 is considered as a “Dead Order”; thus, the record for order 3 is set to a vector of zeroes (Table 7).
Table 4: Aisles to be traversed by orders
Order/aisle / 1 / 2 / 3 / 4 / 5 / 61 / 1 / 1 / 1 / 0 / 1 / 0
2 / 0 / 1 / 1 / 1 / 0 / 1
3 / 1 / 0 / 1 / 1 / 1 / 1
4 / 0 / 1 / 0 / 1 / 0 / 1
Table 5: Partition 1
Order/aisle / 1 / 2 / 3 / 4 / 5 / 61 / 1 / 1 / 1 / 0 / 1 / 0
2 / 0 / 1 / 1 / 1 / 0 / 1
3 / 1 / 0 / 1 / 1 / 1 / 1
4 / 0 / 1 / 0 / 1 / 0 / 1
/ 2 / 3 / 3 / 3 / 2 / 3
Table 6: Partition 2