Thursday, July 28, 2011

Analytic FIFO picking

Analytic functions is a subject I can become quite passionate talking about. How anyone can live without using analytics when programming SQL is beyond me :-)

One of my favorite examples is picking items in our warehouse by First-In First-Out (FIFO). (Similar technique has been parallel evolved by Monty Latiolais as presented by Alex Nuijten at KScope11 - great minds think alike :-) I have demoed this at a DOUG meeting in Copenhagen - here I elaborate a bit on that demo-script.



First we setup a couple of tables with some data:

SQL> create table inventory (
  2     item  varchar2(10),  -- identification of the item
  3     loc   varchar2(10),  -- identification of the location
  4     qty   number,        -- quantity present at that location
  5     purch date           -- date that quantity was purchased
  6  )
  7  /

Table created.

SQL> begin
  2     insert into inventory values('A1', '1-A-20', 18, DATE '2004-11-01');
  3     insert into inventory values('A1', '1-A-31', 12, DATE '2004-11-05');
  4     insert into inventory values('A1', '1-C-05', 18, DATE '2004-11-03');
  5     insert into inventory values('A1', '2-A-02', 24, DATE '2004-11-02');
  6     insert into inventory values('A1', '2-D-07',  9, DATE '2004-11-04');
  7     insert into inventory values('B1', '1-A-02', 18, DATE '2004-11-06');
  8     insert into inventory values('B1', '1-B-11',  4, DATE '2004-11-05');
  9     insert into inventory values('B1', '1-C-04', 12, DATE '2004-11-03');
 10     insert into inventory values('B1', '1-B-15',  2, DATE '2004-11-02');
 11     insert into inventory values('B1', '2-D-23',  1, DATE '2004-11-04');
 12     commit;
 13  end;
 14  /

PL/SQL procedure successfully completed.

SQL> create table orderline (
  2     ordno number,        /* id-number of the order     */
  3     item  varchar2(10),  /* identification of the item */
  4     qty   number         /* quantity ordered           */
  5  )
  6  /

Table created.

SQL> begin
  2     insert into orderline values (1,'A1',24);
  3     insert into orderline values (1,'B1',18);
  4     commit;
  5  end;
  6  /

PL/SQL procedure successfully completed.

We are now ready to start...

We will pick items for sales order number 1.

SQL> variable pick_order number;
SQL> 
SQL> begin
  2     :pick_order := 1;
  3  end;
  4  /

PL/SQL procedure successfully completed.

First let us join the orderlines to the inventory to get all possibilities. If we order by item and purchase date we can "visually" identify what we need to pick:

SQL> select
  2  o.item,
  3  o.qty ord_qty,
  4  i.loc,
  5  i.purch,
  6  i.qty loc_qty
  7  from orderline o
  8  join inventory i
  9     on i.item = o.item
 10  where o.ordno = :pick_order
 11  order by
 12  o.item,
 13  i.purch,
 14  i.loc;

ITEM          ORD_QTY LOC        PURCH       LOC_QTY                            
---------- ---------- ---------- -------- ----------                            
A1                 24 1-A-20     04-11-01         18                            
A1                 24 2-A-02     04-11-02         24                            
A1                 24 1-C-05     04-11-03         18                            
A1                 24 2-D-07     04-11-04          9                            
A1                 24 1-A-31     04-11-05         12                            
B1                 18 1-B-15     04-11-02          2                            
B1                 18 1-C-04     04-11-03         12                            
B1                 18 2-D-23     04-11-04          1                            
B1                 18 1-B-11     04-11-05          4                            
B1                 18 1-A-02     04-11-06         18                            

10 rows selected.

By visual inspection we can see that:
  • Item A1 needs 18 pieces from the oldest location and 6 from the second-oldest.
  • Item B1 needs the entire quantity of the 3 oldest locations plus 3 pieces of the 4th-oldest.
So... how to write SQL that figures out what we can visually see? First let us try an analytic rolling sum:

SQL> select
  2  o.item,
  3  o.qty ord_qty,
  4  i.loc,
  5  i.purch,
  6  i.qty loc_qty,
  7  sum(i.qty) over (
  8     partition by i.item
  9     order by i.purch, i.loc
 10     rows between unbounded preceding and current row
 11  ) sum_qty
 12  from orderline o
 13  join inventory i
 14     on i.item = o.item
 15  where o.ordno = :pick_order
 16  order by
 17  o.item,
 18  i.purch,
 19  i.loc;

ITEM          ORD_QTY LOC        PURCH       LOC_QTY    SUM_QTY                 
---------- ---------- ---------- -------- ---------- ----------                 
A1                 24 1-A-20     04-11-01         18         18                 
A1                 24 2-A-02     04-11-02         24         42                 
A1                 24 1-C-05     04-11-03         18         60                 
A1                 24 2-D-07     04-11-04          9         69                 
A1                 24 1-A-31     04-11-05         12         81                 
B1                 18 1-B-15     04-11-02          2          2                 
B1                 18 1-C-04     04-11-03         12         14                 
B1                 18 2-D-23     04-11-04          1         15                 
B1                 18 1-B-11     04-11-05          4         19                 
B1                 18 1-A-02     04-11-06         18         37                 

10 rows selected.

"over (...)" turns the aggregate sum into an analytic sum.
"partition by" makes the sum work per item (somewhat like "group by").
"order by" tells in which order the rows are added in the rolling sum.
"rows between unbounded preceding and current row" makes it a rolling sum.

With the result of this we see, that when the sum_qty turns greater than the ord_qty, then we have picked sufficient and can stop picking more of that item. Lets try it:

SQL> select
  2  s.*
  3  from (
  4     select
  5     o.item,
  6     o.qty ord_qty,
  7     i.loc,
  8     i.purch,
  9     i.qty loc_qty,
 10     sum(i.qty) over (
 11        partition by i.item
 12        order by i.purch, i.loc
 13        rows between unbounded preceding and current row
 14     ) sum_qty
 15     from orderline o
 16     join inventory i
 17        on i.item = o.item
 18     where o.ordno = :pick_order
 19  ) s
 20  where s.sum_qty < s.ord_qty
 21  order by
 22  s.item,
 23  s.purch,
 24  s.loc;

ITEM          ORD_QTY LOC        PURCH       LOC_QTY    SUM_QTY                 
---------- ---------- ---------- -------- ---------- ----------                 
A1                 24 1-A-20     04-11-01         18         18                 
B1                 18 1-B-15     04-11-02          2          2                 
B1                 18 1-C-04     04-11-03         12         14                 
B1                 18 2-D-23     04-11-04          1         15                 

Well no, that did not quite work... We did not get the last location of each item. What we actually need is to stop, when all the previous rows have contributed enough quantity that we are done picking:

SQL> select
  2  o.item,
  3  o.qty ord_qty,
  4  i.loc,
  5  i.purch,
  6  i.qty loc_qty,
  7  sum(i.qty) over (
  8     partition by i.item
  9     order by i.purch, i.loc
 10     rows between unbounded preceding and 1 preceding
 11  ) sum_prv_qty
 12  from orderline o
 13  join inventory i
 14     on i.item = o.item
 15  where o.ordno = :pick_order
 16  order by
 17  o.item,
 18  i.purch,
 19  i.loc;

ITEM          ORD_QTY LOC        PURCH       LOC_QTY SUM_PRV_QTY                
---------- ---------- ---------- -------- ---------- -----------                
A1                 24 1-A-20     04-11-01         18                            
A1                 24 2-A-02     04-11-02         24          18                
A1                 24 1-C-05     04-11-03         18          42                
A1                 24 2-D-07     04-11-04          9          60                
A1                 24 1-A-31     04-11-05         12          69                
B1                 18 1-B-15     04-11-02          2                            
B1                 18 1-C-04     04-11-03         12           2                
B1                 18 2-D-23     04-11-04          1          14                
B1                 18 1-B-11     04-11-05          4          15                
B1                 18 1-A-02     04-11-06         18          19                

10 rows selected.

By doing "rows between unbounded preceding and 1 preceding", the sum_prv_qty is a sum of loc_qty of all previous rows. Now we can do filtering and stop when sum_prv_qty is greater than or equal to the ordered quantity - or in other words only keep those rows where sum_prv_qty is less than ord_qty:

SQL> select
  2  s.*,
  3  least(s.loc_qty, s.ord_qty - s.sum_prv_qty) pick_qty
  4  from (
  5     select
  6     o.item,
  7     o.qty ord_qty,
  8     i.loc,
  9     i.purch,
 10     i.qty loc_qty,
 11     nvl(sum(i.qty) over (
 12        partition by i.item
 13        order by i.purch, i.loc
 14        rows between unbounded preceding and 1 preceding
 15     ),0) sum_prv_qty
 16     from orderline o
 17     join inventory i
 18        on i.item = o.item
 19     where o.ordno = :pick_order
 20  ) s
 21  where s.sum_prv_qty < s.ord_qty
 22  order by
 23  s.item,
 24  s.purch,
 25  s.loc;

ITEM          ORD_QTY LOC        PURCH       LOC_QTY SUM_PRV_QTY   PICK_QTY     
---------- ---------- ---------- -------- ---------- ----------- ----------     
A1                 24 1-A-20     04-11-01         18           0         18     
A1                 24 2-A-02     04-11-02         24          18          6     
B1                 18 1-B-15     04-11-02          2           0          2     
B1                 18 1-C-04     04-11-03         12           2         12     
B1                 18 2-D-23     04-11-04          1          14          1     
B1                 18 1-B-11     04-11-05          4          15          3     

6 rows selected.

Now we have filtered exactly those locations we need to pick by FIFO. Note the nvl(...,0) - it is necessary because if we left the nulls in there, then the filter predicate "null < s.ord_qty" wouldn't be true :-)

"ord_qty - sum_prv_qty" gives us how much is "left to pick". The least of that and the loc_qty is how much we need to pick at this loc.

And finally we can make our forklift driver happy by picking in location order. This select would be his picking list:

SQL> select
  2  s.loc,
  3  s.item,
  4  least(s.loc_qty, s.ord_qty - s.sum_prv_qty) pick_qty
  5  from (
  6     select
  7     o.item,
  8     o.qty ord_qty,
  9     i.loc,
 10     i.purch,
 11     i.qty loc_qty,
 12     nvl(sum(i.qty) over (
 13        partition by i.item
 14        order by i.purch, i.loc
 15        rows between unbounded preceding and 1 preceding
 16     ),0) sum_prv_qty
 17     from orderline o
 18     join inventory i
 19        on i.item = o.item
 20     where o.ordno = :pick_order
 21  ) s
 22  where s.sum_prv_qty < s.ord_qty
 23  order by
 24  s.loc;

LOC        ITEM         PICK_QTY                                                
---------- ---------- ----------                                                
1-A-20     A1                 18                                                
1-B-11     B1                  3                                                
1-B-15     B1                  2                                                
1-C-04     B1                 12                                                
2-A-02     A1                  6                                                
2-D-23     B1                  1                                                

6 rows selected.

The order by in the analytic clause does not have to match the order by of the complete result. In the analytic clause the order by defines which inventory locations to pick from - the outer order by defines the picking route for the forklift driver.

Which means we can now change our policy for picking simply by changing the analytic order by. For example: "order by i.purch, i.loc" means First-In-First-Out, but if two locations have the same age, then location order is used as "tie-breaker". (It is almost always a good idea to make sure the analytic order by is "unique" to make it deterministic which rows will be chosen in case of "ties" - in this case we order by i.purch to make it FIFO policy, but we add i.loc to the order by to deterministically break ties.)

We could change policy with "order by i.purch, i.qty, i.loc" which would make sure that although we use FIFO we will "clean-up" the smallest amounts first in case of ties. Or we could skip FIFO and simply pick by qty:

SQL> select
  2  s.loc,
  3  s.item,
  4  least(s.loc_qty, s.ord_qty - s.sum_prv_qty) pick_qty
  5  from (
  6     select
  7     o.item,
  8     o.qty ord_qty,
  9     i.loc,
 10     i.purch,
 11     i.qty loc_qty,
 12     nvl(sum(i.qty) over (
 13        partition by i.item
 14        order by i.qty, i.loc   -- << only line changed
 15        rows between unbounded preceding and 1 preceding
 16     ),0) sum_prv_qty
 17     from orderline o
 18     join inventory i
 19        on i.item = o.item
 20     where o.ordno = :pick_order
 21  ) s
 22  where s.sum_prv_qty < s.ord_qty
 23  order by
 24  s.loc;

LOC        ITEM         PICK_QTY                                                
---------- ---------- ----------                                                
1-A-20     A1                  3                                                
1-A-31     A1                 12                                                
1-B-11     B1                  4                                                
1-B-15     B1                  2                                                
1-C-04     B1                 11                                                
2-D-07     A1                  9                                                
2-D-23     B1                  1                                                

7 rows selected.

That example would clean up small quantities first to free up space in our warehouse quickly. If we have lot of space available we might wish to optimize for speed with as few picks as possible:

SQL> select
  2  s.loc,
  3  s.item,
  4  least(s.loc_qty, s.ord_qty - s.sum_prv_qty) pick_qty
  5  from (
  6     select
  7     o.item,
  8     o.qty ord_qty,
  9     i.loc,
 10     i.purch,
 11     i.qty loc_qty,
 12     nvl(sum(i.qty) over (
 13        partition by i.item
 14        order by i.qty desc, i.loc   -- << only line changed
 15        rows between unbounded preceding and 1 preceding
 16     ),0) sum_prv_qty
 17     from orderline o
 18     join inventory i
 19        on i.item = o.item
 20     where o.ordno = :pick_order
 21  ) s
 22  where s.sum_prv_qty < s.ord_qty
 23  order by
 24  s.loc;

LOC        ITEM         PICK_QTY                                                
---------- ---------- ----------                                                
1-A-02     B1                 18                                                
2-A-02     A1                 24                                                

Or we might prefer to pick warehouse 1 as first priority to minimize time driving around the warehouses:

SQL> select
  2  s.loc,
  3  s.item,
  4  least(s.loc_qty, s.ord_qty - s.sum_prv_qty) pick_qty
  5  from (
  6     select
  7     o.item,
  8     o.qty ord_qty,
  9     i.loc,
 10     i.purch,
 11     i.qty loc_qty,
 12     nvl(sum(i.qty) over (
 13        partition by i.item
 14        order by i.loc   -- << only line changed
 15        rows between unbounded preceding and 1 preceding
 16     ),0) sum_prv_qty
 17     from orderline o
 18     join inventory i
 19        on i.item = o.item
 20     where o.ordno = :pick_order
 21  ) s
 22  where s.sum_prv_qty < s.ord_qty
 23  order by
 24  s.loc;

LOC        ITEM         PICK_QTY                                                
---------- ---------- ----------                                                
1-A-02     B1                 18                                                
1-A-20     A1                 18                                                
1-A-31     A1                  6                                                

Using this technique we can easily separate policy of which locations to choose to pick from which order those locations should be visited by the picker.

The complete script of all of the above can be found here, and a sample spool output of running the script is here. Oracle documentation tells you all syntax on analytic functions.

Have fun with analytics - they rock and roll (as Tom Kyte is fond of saying :-)

No comments:

Post a Comment