PATENT ABSTRACT
In one aspect, a computer-implemented method is provided for aggregating and scheduling product batches in a manufacturing environment. Using a batch aggregation engine implementing a mathematical programming strategy, one or more product demands are allocated to one or more product batches having suggested sizes and suggested starting times. The mathematical programming strategy includes evaluating a number of time-based penalties relative to one another in allocating the demands to the batches, the time-based penalties being based on relationships between suggested starting times for batches and times of demands being considered for allocation to batches. The suggested sizes, the suggested starting times, and feedback relating to the suggested sizes and suggested starting times are communicated from the batch aggregation engine to a scheduling engine to assist the scheduling engine in scheduling starting times for the batches.

PATENT DESCRIPTION
RELATED APPLICATIONS  
       [0001]    This application is a continuation of U.S. application Ser. No. 10/393,793, entitled “Collaboratively Solving an Optimization Problem Using First and Second Optimization Software Each Having at Least Partial Information Concerning the Optimization Problem,” now pending, which is a continuation of U.S. application Ser. No. 09/520,669, entitled “System and Method for Collaborative Batch Aggregation and Scheduling,” now U.S. Pat. No. 6,560,501 B1. 
     
    
     
       TECHNICAL FIELD OF THE INVENTION  
         [0002]    This invention relates generally to the field of aggregating and scheduling batches in a manufacturing environment, and more particularly to collaborative batch aggregation and scheduling in a manufacturing environment.  
         BACKGROUND  
         [0003]    The manufacture of products or other items commonly involves a multi-stage process that includes the use of equipment of various capacities. In such a multi-stage, variable equipment size process, product or end-item demands are often aggregated or split into manufacturing batches in order to fit the available equipment sizes. The scheduling of these batches must account for the complex factory flows between the manufacturing stages and as well as various business rules unique to the particular industry involved. If the manufacturing process is used to produce multiple products, the scheduling process also preferably minimizes sequence-dependent equipment changeovers between the scheduled batches.  
           [0004]    Computer implemented planning and scheduling systems are often used for manufacturing and other supply chain planning functions. In general, such systems can model the manufacturing and related environments and provide plans or schedules for producing items to fulfill consumer demand within the constraints of the environment. Existing scheduling systems, however, typically cannot handle variable equipment sizes or make optimal batching decisions using a number of different criteria. Often a manual heuristic scheme is used, based on the personal expertise of a human operator, to divide demand for a product into batches of a single size and to schedule the batches. However, these heuristic schemes often lead to unsatisfactory factory schedules in terms of under-utilized resources, late deliveries, excess inventories, and overall unbalanced factories. Moreover, they necessarily require a person with detailed knowledge of and extensive experience with the manufacturing process for which the batch aggregation and scheduling is required. These and other deficiencies make previous systems and methods for aggregating and scheduling batches inadequate for many purposes.  
         SUMMARY OF THE INVENTION  
         [0005]    According to the present invention, disadvantages and problems associated with previous batch aggregation and scheduling techniques may be reduced or eliminated.  
           [0006]    In one aspect, a computer-implemented method is provided for aggregating and scheduling product batches in a manufacturing environment. Using a batch aggregation engine implementing a mathematical programming strategy, one or more product demands are allocated to one or more product batches having suggested sizes and suggested starting times. The mathematical programming strategy includes evaluating a number of time-based penalties relative to one another in allocating the demands to the batches, the time-based penalties being based on relationships between suggested starting times for batches and times of demands being considered for allocation to batches. The suggested sizes, the suggested starting times, and feedback relating to the suggested sizes and suggested starting times are communicated from the batch aggregation engine to a scheduling engine to assist the scheduling engine in scheduling starting times for the batches.  
           [0007]    Particular embodiments of the present invention may provide one or more technical advantages. For example, according to decisions and associated feedback communicated between first and second optimization software, the first and second optimization software may collaborate to provide a suitable solution, such as a batch aggregation and scheduling solution where the first optimization software includes batch aggregation software and the second optimization software includes scheduling software. Certain embodiments may allow demands for a product or other item to be aggregated into or split between batches, while also allowing the batches to be scheduled in a manner that increases factory throughput and reduces manufacturing costs. Certain embodiments may be capable of aggregating batches of variable size across multiple production stages and computing material flows between these stages. By allowing for variable batch sizes, certain particular embodiments may enable the use of a variety of equipment sizes in the manufacturing process and optimizes the use of each of these equipment sizes. Certain embodiments may reduce the quantity of work-in-process, minimize end-item inventory, and reduce product shortages and late deliveries. Certain embodiments may be used to optimize other manufacturing and supply chain planning processes, according to particular needs. One or more other technical advantages may be readily apparent to those skilled in the art from the figures, descriptions, and claims included herein.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0008]    To provide a more complete understanding of the present invention and further features and advantages thereof, reference is now made to the following description taken in conjunction with the accompanying drawings, in which:  
         [0009]    [0009]FIG. 1 illustrates an example system that executes a collaborative batch aggregation and scheduling process to optimize the manufacture of an item;  
         [0010]    [0010]FIG. 2 illustrates an example collaborative batch aggregation and scheduling process;  
         [0011]    [0011]FIG. 3 illustrates an example workflow to which a collaborative batch aggregation and scheduling process may be applied;  
         [0012]    [0012]FIG. 4 illustrates an example allocation of demands to batches using a collaborative batch aggregation and scheduling process;  
         [0013]    FIGS.  5 A- 5 D illustrate the relationship between example variables and parameters for use in a collaborative batch aggregation and scheduling process; and  
         [0014]    [0014]FIG. 6 illustrates an example penalty table for use in a collaborative batch aggregation and scheduling process.  
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0015]    [0015]FIG. 1 illustrates an example system  10  that executes a collaborative batch aggregation and scheduling process  12  to optimize the manufacture, packaging, or other handling of a product. The term “product” should be interpreted to encompass any appropriate item or component that might be subject to batch aggregation and scheduling, including any unfinished item or component associated with any stage in a manufacturing, packaging, or other appropriate process. In one embodiment, process  12  involves two engines: a batch aggregation engine  20  and a scheduling engine  30 . Batch aggregation engine  20  creates and aggregates product batches according to suitable aggregation criteria described more fully below. All forms of the term “aggregate” should be interpreted to include splitting or dividing a product demand between multiple batches, as well as combining product demands into a batch. In one embodiment, as described more fully below, batch aggregation engine  20  uses mixed-integer linear programming (MILP) to optimize the aggregation of product demands into batches to meet various manufacturing, shipping, customer or other related criteria.  
         [0016]    Scheduling engine  30  schedules the aggregated batches according to suitable scheduling criteria. Scheduling engine  30  may include a task-based scheduling system suitable for handling scheduling constraints and minimizing sequence-dependent set-ups, for example only and not by way of limitation, the RHYTHM OPTIMAL SCHEDULER produced by i2 TECHNOLOGIES, INC. and described in U.S. Pat. No. 5,319,781. Batch aggregation engine  20  and scheduling engine  30  cooperate in a collaborative cycle in which the output  22  of aggregation engine  20  serves as input to scheduling engine  30 , and the output  32  of scheduling engine  30  serves as input to aggregation engine  20 . Such a combination of similarly collaborating engines may be used according to the present invention to optimize the manufacture, packaging, or other handling of any suitable product that is created in batches. Those skilled in the art will appreciate that the present invention may also be used for batch aggregation, scheduling, or both batch aggregation and scheduling in other supply chain planning applications (for example, aggregating and scheduling shipments of products), and that the present invention encompasses all such applications. In addition, batch aggregation engine  20  and scheduling engine  30  may be thought of generically as two optimization engines having partial information about an overall optimization problem. Each engine solves a sub-problem of the overall problem based on its partial information, and the two engines collaboratively pass the solutions to their sub-problems until a sufficiently optimal solution to the overall optimization problem is obtained. Any number of such optimization engines collaboratively working to solve an optimization problem are encompassed by the present invention.  
         [0017]    Engines  20  and  30  may operate on one or more computers  14  at one or more locations. Computer  14  may include a suitable input device, such as a keypad, mouse, touch screen, microphone, or other device to input information. An output device may convey information associated with the operation of engines  20  and  30 , including digital or analog data, visual information, or audio information. Computer  14  may include fixed or removable storage media, such as magnetic computer disks, CD-ROM, or other suitable media to receive output from and provide input to engines  20  and  30 . Computer  14  may include a processor and volatile or non-volatile memory to execute instructions and manipulate information according to the operation of engines  20  and  30 . Although only a single computer  14  is shown, engines  20  and  30  may each operate on separate computers  14 , or may operate on one or more shared computers  14 , without departing from the intended scope of the present invention.  
         [0018]    User or automated input  16  may be provided to engines  20  and  30  for use in batch aggregation and scheduling. For example, input  16  may include information about the available capacity and set-up of manufacturing equipment that is entered by a user or automatically supplied by the equipment itself (for example, through the use of sensors). Input  16  may also include one or more demands for a product, the “soft” and “hard” dates by which the demanded product is to be delivered or shipped, and appropriate business rules that affect the manufacturing process (for example, the severity of shipping a particular order late or the cost of storing inventory of a product). As described below, process  12  uses input  16  to aggregate and schedule product batches according to the operation of collaborating engines  20  and  30 . The resulting solution, which may include a schedule for making a series of product batches of various sizes using various pieces of equipment, may then be provided to a user, a manufacturing control computer, or any other suitable device related to the manufacturing process as output  18 .  
         [0019]    [0019]FIG. 2 illustrates an example collaborative batch aggregation and scheduling process  12 . As described above, batch aggregation engine  20  and scheduling engine  30  cooperate in a collaborative cycle to reach a suitably optimal solution. Within process  12 , batch aggregation engine  20  and scheduling engine  30  iteratively attempt to optimize their respective solutions to the overall aggregation and scheduling problem by sharing their respective outputs  22  and  32 . Batch aggregation engine  20  communicates output  22  in the form of decisions  24  and feedback  26  relating to decisions  24 . Scheduling engine  30  communicates output  32  in the form of decisions  34  and feedback  36  relating to decisions  34 . For example, decisions  24  that batch aggregation engine  20  may output may include one or more suggested start times and sizes for each aggregated batch. Decisions 34 output by scheduling engine  30  may include at least one scheduled start time and size for each batch. However, not all decisions  24  made by batch aggregation engine  20  typically need to be or even can be followed by scheduling engine  30 . Similarly, not all of the decisions  34  made by scheduling engine  30  typically need to be or even can be followed by batch aggregation engine  20 . Each of the engines  20  and  30  is suited to optimize one part of the overall solution, but neither may be able to optimally solve the overall problem by itself. According to the present invention, engines  20  and  30  cooperate to solve the problem and allow appropriate decisions to be made by the best-qualified engine.  
         [0020]    For engines  20  and  30  to collaboratively determine a suitably optimal solution, each engine  20  and  30  may pass various penalties as feedback  26  and  36 , respectively, relating to its decisions  24  and  34 , respectively, that indicate the relative severity of or are otherwise associated with deviating from those decisions. The engine  20  and  30  receiving these penalties weighs the penalties against the information of which it is aware when determining its own decisions  24  and  34 , respectively. By iteratively passing decisions and penalties associated with deviating from these decisions, each engine  20  and  30  can thereby influence the decisions of the other engine to collaboratively optimize the manufacturing process.  
         [0021]    As an example, assume that there are a series of expected demands  40  for a product over a time horizon  42 . Each demand  40  may be associated with an order placed by a customer to be delivered at a particular time in time horizon  42 . Batch aggregation engine  20  initially generates a sequence of batches  50  from which to meet demands  40  and determines which demand or demands  40  each batch will be used to meet. In the particular example illustrated in FIG. 2, batch aggregation engine  20  determines that demand  40   a  will be met from batch  50   a , which has a suggested size and a suggested start time along time horizon  42 . Similarly, batch aggregation engine  20  initially determines that demands  40   b ,  40   c  and  40   d  will all be met from a single batch  50   b , which has a suggested size and a suggested start time that is later in time horizon  42  than the suggested start time for batch  50   a . The sizes of batches  50   a  and  50   b  may be different, reflecting different sizes of equipment associated with the manufacture of batches  50   a  and  50   b.    
         [0022]    To make these initial decisions  24 , batch aggregation engine  20  typically will have information about product demands  40  and about the equipment available to make product batches  50  to meet demands  40 . Batch aggregation engine  20  sends decisions  24  to scheduling engine  30  and, together with or separate from decision  24 , also sends feedback  26  in the form of one or more penalties indicating the severity of or otherwise associated with deviating from at least one of the suggested batch sizes or starting times. For example, penalties  26  may include, but are not limited to, a penalty for scheduling a particular batch  50  such that a particular demand  40  is not timely met, a penalty for scheduling a particular batch  50  such that the resulting product will have to be held as inventory before being delivered to the customer or other entity demanding the product, a penalty for using a single batch  50  to meet a demand  40  for two or more packaging sizes, and a penalty for partially utilizing a shipping pallet to meet a demand  40 . Other suitable penalties  26  are described in further detail below, although the present invention is intended to encompass all appropriate penalties, whether or not specifically described herein.  
         [0023]    After scheduling engine  30  receives the initial decisions  24  and penalties  26  from batch aggregation engine  20 , scheduling engine  30  schedules batches  50   c  and  50   d  of specified sizes (which may or may not be the sizes suggested by batch aggregation engine  20 ) to begin at specific times  44  along time horizon  42 . Scheduling engine  30  determines the actual starting times of batches  50   c  and  50   d  according to the suggested start times and sizes received from batch aggregation engine  20 , the penalties associated with deviating from these suggested sizes and times, and other information scheduling engine  30  may have about the problem, such as the availability of resources, capacity and current set-up state of production equipment, changeover costs associated with changing the current set-up state, labor constraints, material availability, and any other suitable information. Although two batches  50   c  and  50   d  are illustrated, scheduling engine  30  may schedule more or fewer batches  50  according to particular needs. Scheduling engine  30  schedules the aggregated batches  50 , but may have the flexibility not to schedule one or more batches  50 . Scheduling engine  30  then sends the actual scheduled starting times of the suggested batch sizes, the actual scheduled starting times and batch sizes of batches not suggested by engine  20 , or any combination of these as decisions  34  to batch aggregation engine  20 , together with or separate from feedback  36  in the form of one or more appropriate penalties associated with deviating from the scheduled times, sizes, or both times and sizes. In one embodiment, such penalties may discourage the use of over-utilized production resources, may encourage the use of under-utilized resources, may relate to peggings between upstream and downstream batches, or may relate to the compatibility of batches with demands or the compatibility of batches with downstream batches. As an example, penalties  36  may include, but are not limited to, a penalty for deviating from a certain scheduled batch size to encourage the full use of one or more pieces of production equipment over a specified time period or a penalty associated with the changeover time or cost associated with changing the type of product manufactured in a particular piece of manufacturing equipment. Other suitable penalties, whether or not relating to the capacity and operation of the manufacturing equipment or other resources, may be used instead of or in addition to the penalties described above.  
         [0024]    The collaborative batch aggregation and scheduling process  12  iterates in a loop until a suitably optimal solution is achieved (for example, when the solutions from each engine  20  and  30  have sufficiently converged or a predetermined number of iterations has been reached). Given the decisions  34  and feedback  36  from scheduling engine  30 , batch aggregation engine  20  can re-aggregate demands  40  into batches  50  to achieve a revised solution that is closer to optimal. Batch aggregation engine  20  may output this revised solution as decisions  24  and feedback  26 , to be followed by rescheduling and output of a revised solution as decision  34  and feedback  36  from scheduling engine  30 . The present invention contemplates some or all of decisions  24  and feedback  26  from batch aggregation engine  20 , or decisions  34  and feedback  36  from scheduling engine  30 , remaining unchanged from one iteration to the next, as appropriate. The best overall solution to the problem may be stored in memory and provided to a user or a manufacturing-related device (either after meeting a predetermined threshold or after a predetermined number of iterations). In this manner, the iterative process provides for collaborative optimization between possibly very different engines that are applied to solve separate, but related, portions of a larger optimization problem (for example, batch aggregation versus scheduling). Furthermore, although the above example describes a single-stage (product batch to end-item demand) and single-product manufacturing process, process  12  can be advantageously applied to any suitable multi-stage and multi-product manufacturing and shipping problem as described below.  
         [0025]    [0025]FIG. 3 illustrates an example workflow  100  used in the manufacture, packaging, and shipping of paint, to which the collaborative batch aggregation and scheduling process  12  of the present invention may be applied. Although the example described below involves the manufacture, packaging, and shipping of paint, any other appropriate workflow involving the aggregation of any product, item, or component into batches may also be optimized using the present invention. In the illustrated embodiment, workflow  100  begins with a pre-mix stage  112  that employs a number of pre-mix tanks  110 . Pre-mix tanks  110  are used to prepare materials to be used in a subsequent paint mixing stage  122 . Mixing stage  122  employs a collection of mixing tanks  120  that each mix materials from the pre-mix stage to form selected colors of paint. The paint colors are typically dependant on the types of pre-mix materials used in mixing stage  122 . In workflow  100 , there are three mixing tanks  120   a ,  120   b , and  120   c  which may be used to simultaneously mix different (or the same) colors of paint. After the paint has been mixed, it is routed to fill stage  132  to be placed in containers using one or more fill lines  130 . In workflow  100 , there are two fill lines: a gallon fill line  130   a  and a quart fill line  130   b , although any suitable number of fill lines  130  could be used according to particular needs. Therefore, in this particular example, the various colors of paint mixed in mixing stage  122  can be placed in either one-gallon or one-quart containers. After the paint has been packaged at fill stage  132 , the filled paint containers are transported to a palletization stage  140  to be grouped and palletized for shipping to a number of distributors  150  at distribution stage  152 .  
         [0026]    Workflow  100  therefore presents an example multi-stage (for example, pre-mix, mix, fill, palletization, distribution, or any other suitable combination of stages) and multi-product (for example, various combinations of chemical consistency, color, fill container size, and any other suitable product variables) manufacturing process. Although the end-item demands  40  for workflow  100  are the orders of each distributor  150  for the paint products, each stage in workflow  100  may be considered to place a demand  40  for the “product” from the previous stage. In addition, although not illustrated, workflow  100  may include other suitable stages, such as the supply of raw materials to the pre-mix stage and the supply of paint to retail customers from distributors  150 .  
         [0027]    Collaborative batch aggregation and scheduling process  12  may be used to compute material flows across these various stages and to assign or “peg” downstream demands  40  (either demands for a finished product or demands for batches of an unfinished product associated with one of these stages) to upstream batches  50  while meeting appropriate business rules and optimization criteria. In one embodiment, batch aggregation engine  20  is used to aggregate demands  40  into batches  50  according to one or more appropriate cost criteria. For example, and not by way of limitation, engine  20  may aggregate batches  50  so as to minimize product shortages and product inventory (“just in time” manufacturing), avoid pallet fragmentation (only one partial pallet per batch  50 ), meet demand from multiple distributors evenly, or minimize split-fills (using a batch  50  to fill multiple container sizes), singly or in any suitable combination. Output  22  of batch aggregation engine  20 , including decisions  24  and feedback  26 , is provided to scheduling engine  30 , which may tentatively schedule batches  50  so as to minimize sequence-dependent set-up times, minimize costs, maximize throughput, or meet any other suitable objective or objectives. Scheduling engine  30  may provide this suggested schedule to batch aggregation engine  20 , as decisions  34  and feedback  36 . As described above, batch aggregation engine may use this information to re-optimize the batch aggregation solution. This cycle is continued according to the present invention until an optimal or sufficiently optimal solution is obtained, or until a predetermined number of iterations is reached.  
         [0028]    [0028]FIG. 4 illustrates an example allocation of demands  40  to batches  50  that might be obtained using batch aggregation engine  20 , again using the paint manufacturing process as merely an illustrative example. A table  200  is used to illustrate demands  40  at four time slots  210  for a particular color of paint. Demands  40  are made in this case by two paint distributors  220   a  and  220   b , although more or fewer distributors may be involved according to particular needs. To meet demands  40 , batch aggregation engine  20  creates three different paint batches  50   a ,  50   b , and  50   c . Batches  50   a  and  50   b  are each manufactured in 150-gallon mixing tanks  202  and  204 , respectively. Batch  50   c  is manufactured in a 400-gallon mixing tank  206 . Batch  50   a  totals 145 gallons, such that a small portion of the capacity of tank  202  remains unused. Batches  50   b  and  50   c  use the entire capacity of their respective tanks  204  and  206 , and thus total 150-gallons and 400-gallons, respectively. The example batch aggregation of FIG. 4 has taken palletization into account by minimizing partially-filled pallets (assuming the pallet size of both gallon and quart pallets is twenty units per pallet.)  
         [0029]    As illustrated in FIG. 4, batches  50   a  and  50   b  are each used to meet multiple product demands  40  which arise from multiple distributors  220 . These demands  40  are also for multiple container sizes and for different time slots  210 . Specifically, batch  50   a  is used to meet all 30-gallons of demand  40   a , 15-gallons of demand  40   b , and 100-gallons of demand  40   e . Batch  50   b  is used to meet the other 20 gallons of demand  40   b , all 20 quarts (5 gallons) of demand  40   c , all 180-quarts (45 gallons) of demand  40   d , 30-gallons of demand  40   e , and all 50-gallons of demand  40   f . Batch  50   c , on the other hand, is used to meet only one demand  40  from one distributor  220  for one container size. Specifically, batch  50   c  is used to meet the remaining 400-gallons of demand  40   e.    
         [0030]    As described above, such an allocation or aggregation of demands  40  into batches  50  may be obtained using an MILP model in batch aggregation engine  20 . A significant advantage of an MILP approach over manual or other heuristic aggregation techniques is that it allows for a declarative yet flexible formulation of customer-specific aggregation rules and objectives. To use the MILP approach, the problem is preferably broken down into aggregation classes, which in the case of example workflow  100  may each be a particular color of paint for which there is a demand  50  on time horizon  42 . Thus, for each color of paint, batch aggregation engine  20  may separately aggregate the product demands  40  (of each of the stages) into batches  50 .  
         [0031]    In the initial aggregation phase (the first iteration in the cycle of process  12 ), no batches  50  may yet exist. Therefore, new batches  50  need to be created before assigning demands  40  to batches  50 . One complication related to the creation of batches  50  is the fact that workflow  100  may contain tanks of different sizes. Therefore, the batch size generally cannot be specified before a tank is assigned. To optimize batch scheduling, it is preferable that scheduling engine  30  retains the flexibility to assign batches  50  to tanks according to the actual or projected workloads of the tanks. Thus, by deferring to scheduling engine  30  the decision of which batches  50  of a given paint color to schedule, better results may be achieved in terms of throughput since the workload may be balanced across the different equipment sizes. To accomplish this, batch aggregation engine  20  may create a variety of different sizes of batches  50  and prepare a batch penalty table, described more fully below, for each batch  50  to assist scheduling engine  30  in scheduling batch  50 . For demands  40  that have been aggregated to batches  50  but for which scheduling engine  30  has decided not to schedule or to schedule late with respect to their associated due dates, re-aggregation by aggregation engine  20  offers the chance to eventually meet all demands  40  timely in the final schedule by re-pegging those demands  40  to the batches  50  that have been scheduled.  
         [0032]    In one embodiment, the integrated problem of batch creation, batch sizing, and demand aggregation is approached by creating empty batches  50  that are fixed in time but variable in size (referred to as flex-batches) during a heuristic pre-processing stage. The flex-batches are input to batch aggregation engine  20 , which determines the size (possibly zero) of the flex-batches and allocates demands  40  to batches  50  while keeping the starting times of the flex-batches fixed. The freedom that engine  20  has to determine the allocations depends on how many flex-batches are created in the pre-processing stage. In general, the greater number of flex-batches created (for example, creating a flex-batch for every minute on time horizon  42  versus creating a flex-batch for every day on time horizon  42 ), the more freedom engine  20  has to assign demands  40  to batches  50 . However, increased freedom may be associated with an increased processing time, since the determination as to which of the excess batches  50  to leave empty typically enlarges the complexity of the calculations.  
         [0033]    Once the flex-batches have been created, batch aggregation engine  20  may use the following example MILP model to optimize the batch aggregation process for workflow  100 . In a particular embodiment, the model defines the following indices or sets (which are provided as examples and should not be interpreted as limiting the model) to be used in the calculations as follows:  
                                       i ∈ P   Pre-mix batches       j ∈ M   Mix batches       n ∈ P ∪ M   Overall batches, including pre-mix batches and mix batches       k ∈ D   Demands, either make to stock or make to order       k ∈ D f    ⊂  D   Demands of fill size f       f ∈ F   Fill sizes for packing       s ∈ S n    ⊂  S   Possible sizes for batch n (currently S n  = S).                  
 
         [0034]    The following parameters (which are provided as examples and should not be interpreted as limiting the model) may be used by the model and values for these parameters input to engine  20 :  
                                   Name   Description                               d k     Size of demand k       ru k     Maximum roundup demand allowed with           demand k       u ns     Possible sizes of batch n       x ns     Lower limit on amount of batch that can be           used without “excess” slack penalty       l ns     Lowest limit on amount of batch used, if           batch is of size s (a physical constraint)           Note: l ns  ≦ x nd  ≦ u us                                   u   n     =       max   s          u   ns                     bsl   n   max     =       max   s          (       u   ns     -     x   ns       )                     besl   n   max     =       max   s          (       x   ns     -     l   ns       )                                             Maximum possible size of batch n               asp   Maximum number of split fills allowed           per batch       t k     Due date of demand k       t n     Time when the batch is scheduled (for           inventory and lateness calculations)       b ij     Material expansion factor for pre-mix           i to mix j                  
 
         [0035]    The following variables (which are provided as examples and should not be interpreted as limiting the model) may be used in the model&#39;s objectives (which are described below):  
                                       Name   Domain   Description                   bs n     [0, u n ]   Batch size available       bu n     [0, u n ]   Batch size actually used       bsl n     [0, bsl n   max ]   Allowable batch slack       besl n     [0, besl n   max ]   Excess slack above maximum       bb ns     {0, 1}   Batch size binary       pm ij     [0, u n ]   Amount of pre-mix batch i supplied to mix batch j       md jk     [0, min(u n , d k )]   Amount of mix batch j supplied to demand k       r k     [0, ru k ]   Roundup or phantom demand allowed with               demand k (may be 0)       mf jf     {0, 1}   Mix batch j includes SKUs f pack (fill) size f       me fi     [0, |F|-asp]   Number of split fills exceeding asp in mix batch               j, where |F| is the size of set F.                  
 
         [0036]    FIGS.  5 A- 5 D illustrate several of the above variables and parameters relating to the batch sizes and the amount of batch slack (the amount of unused capacity of a pre-mix or mixing tank). FIG. 5A shows the relationship between these variables when a tank  240  (either a pre-mix or a mixing tank) is filled to a minimum operational level  242 . FIG. 5B shows the relationship between these variables when tank  240  is filled to a level  244  above minimum operational level  242 , but below a preferable minimum level  246 . FIG. 5C shows the relationship between these variables when tank  240  is filled to a level  248  above preferable minimum level  246 , but below a maximum operational level  250 . FIG. 5D shows the relationship between these variables when tank  240  is filled to maximum operational level  250 .  
         [0037]    The following weights (which are provided as examples and should not be interpreted as limiting the model) may also be included in the model objectives. The weights are each given a value according to particular needs and are input into batch aggregation engine  20 :  
                                                   Name   Description                           wpl   Pre-mix earliness           wpe   Mix earliness           wml k     Lateness for demand k           wme k     Earliness for demand k           wps   Pre-mix slack           wpes   Pre-mix excess slack           wms   Mix slack           wmes   Mix excess slack           wf   Split fills           wef   Excess split fills           wr k     Roundup or phantom demand           wpbb s     Price for using any pre-mix batch of size s           wmbb s     Price for using any mix batch of size s                      
 
         [0038]    Note: wpbb s  and wmbb s  are used to balance the equipment load across sizes  
         [0039]    In one embodiment, after suitable parameters and weights have been input to batch aggregation engine  20 , engine  20  aggregates demands  40  into batches  50  such that the sum of the following objectives (which are provided as examples and should not be interpreted as limiting the model) are minimized:  
                                                           1.           wpl          ∑     i   ∈   P              ∑     j   ∈     M   :       t   i     &gt;     t   j                    (       t   i     -     t   j       )     ·     pm   ij                                     Lateness of pre-mix batches (delays mix batch processing)               2.             w      pe            ∑     i   ∈   P              ∑     j   ∈     M   :       t   i     &gt;     t   j                    (       t   j     -     t   i       )     ·     pm   ij                                     Earliness (work-in-process) of pre-mix batches               3.             ∑     k   ∈   D              wml   k            ∑     j   ∈     M   :       t   j     &gt;     t   k                    (       t   j     -     t   k       )     ·     md   jk                                     Lateness of mix batches (penalty will differ for orders and stock)               4.             ∑     k   ∈   D              wme   k            ∑     j   ∈     M   :       t   j     &lt;     t   k                    (       t   k     -     t   j       )     ·     md   jk                                     Earliness (end-item inventory) of mix batches               5.             wf          ∑     j   ∈   M              ∑     f   ∈   F            mf   jf           +     wef          ∑     j   ∈   M            mef   j                                   Split fills, plus excess split fills               6.             ∑     k   ∈   D              wr   k          r   k                                 Roundup/phantom inventory               7.             wps          ∑     i   ∈   P            bsl   i         +     wpes          ∑     i   ∈   P            besl   i                                   Slacks of partially filled pre-mixing tanks               8.             wms          ∑     j   ∈   M            bsl   j         +     wmes          ∑     j   ∈   M            besl   j                                   Slacks of partially filled mixing tanks               9.             ∑     i   ∈   P              ∑     s   ∈     S   i                wpbb   s     ·     bb   is                                   Cost for using a pre-mix batch of size s               10.             ∑     j   ∈   M              ∑     f   ∈     S   j                wmbb   s     ·     bb   js                                   Cost for using a mix batch of size s                  
 
         [0040]    In one embodiment, batch aggregation engine  20  operates to minimize the sum of one or more of these or other suitable objectives. When determining, in a particular embodiment, the optimal batch aggregation using these objectives, the following constraints (which are provided as examples and should not be interpreted as limiting the model) may be followed:  
         [0041]    Constraints on All Batches  
                                                           1.             bs   n     =       bu   n     +     bsl   n     +       besl   n                     ∀     n   ∈     P   ⋃   M                                       Size of batch is amount used + slack + excess slack               2.             bs   n     =       ∑     s   ∈     S   n                  u   ns     ·     bb   ns                       ∀     n   ∈     P   ⋃   B                                       Size of each batch depends on the binary selected               3.                 l   ns          bb   ns       ≤       bu   n                     ∀     n   ∈     P   ⋃   B             ,     s   ∈     S   n                                 Amount of batch used must meet minimum if it is that size               4.               bsl   n     ≤       (       u   ns     -     x   ns       )          bb   ns                     ∀     n   ∈     P   ⋃   B             ,     s   ∈     S   n                                 Upper limit on bsl n , depending on batch size               5.               besl   n     ≤       (       x   ns     -     l   ns       )          bb   ns                     ∀     n   ∈     P   ⋃   B             ,     s   ∈     S   n                                 Upper limit on besl               6.               ∑     s   ∈     S   n              bb   ns       ≤     1                   ∀     n   ∈     P   ⋃   B                                     At most one size variable can be selected                  
 
         [0042]    Constraints on Mix Batches  
                                                           1.             bu   j     =       ∑     k   ∈   D              md   jk                     ∀     j   ∈   M                                     Sum of mix batch used must equal total demand supplied               2.               bu   j     =       ∑     i   ∈   P              b   ij          pm   ij           ,                ∀     j   ∈   M                                 Mix batch used equals scaled amount of pre-mix batch               3.                 ∑     k   ∈     D   f              md   jk       ≤       u   j          mf   if                     ∀     j   ∈   M           ,     f   ∈   F                               The md jk  variable is 1 if there is a fill of that size               4.                 ∑     f   ∈   F            mf   if       -   asp     ≤       mef   j                     ∀     j   ∈   M                                   No more than asp fill sizes per batch (split-fills)                  
 
         [0043]    Constraints on Pre-Mix Batches  
                                                           1.             bu   i     =       ∑     j   ∈   M              pm   ij                     ∀     i   ∈   P                                     Pre-mix batch used is sum supplied to mix batches               2.                 ∑     j   ∈   M            md   jk       =       d   k     +     r   k         ,                ∀     k   ∈   N                                 Supply total demand for order +roundup (phantom demand that is created)                  
 
         [0044]    Using the model described above, in which the sum of the objectives may be minimized according to appropriate constraints, batch aggregation engine  20  is able to aggregate demands  40  for a color of paint (or any other suitable product, item, or component) into batches  50  of different discrete sizes by optimizing material flows across several production stages. The model allows for flexible batch sizes that are desirable for handling different tank fill-levels and minimizing batch slacks. Using the model, batch aggregation engine  20  also helps to reduce the amount of work-in-process, minimize end-item inventory, reduce shortages and lateness of deliveries and reduce split fills. The model described above may be extended, as appropriate, to compute an allocation of pallets to batches  50 , minimize partial pallets, and maximize the fairness or equality between supplies to different distributors.  
         [0045]    After batch aggregation engine  20  has performed the optimization described above, engine  20  outputs to scheduling engine  30 , as decisions  24 , the created batches  50  with suggested starting times for each batch  50  that was created. In addition to the suggested batch starting times and sizes, engine  20  outputs feedback  26 , in the form of penalties or otherwise, for each batch  50  to be used by scheduling engine  30 . Penalties may be communicated to scheduling engine  30  individually or in the form of one or more penalty tables or other groupings.  
         [0046]    [0046]FIG. 6 illustrates an example penalty table  300  produced by batch aggregation engine  20  that provides information to scheduling engine  30  regarding the effect of deviating from the suggested starting time for a particular batch  50 . Penalty table  300  is a mapping of penalty values over time for batch  50 . In the illustrated embodiment, penalty table  300  includes penalties indicating the effect on the amount of product shortage and product inventory of moving the starting time of batch  50 . However, penalty table  300  may include one or more penalties (instead of or in addition to those described above) associated with any suitable variable or criterion considered by batch aggregation engine  20 . Penalty table  300  illustrates that as the batch manufacturing time progresses, the overall inventory penalty decreases. The present invention contemplates penalty table  300  of any suitable shape according to one or more appropriate business rules. For example, if a business rule specifies that no late deliveries are to be made, then as manufacturing time progresses and due dates are missed, the overall slope of the inventory penalty decreases. Conversely, as manufacturing time progresses and “soft” due dates are missed, the shortage penalty slope  320  increases (due to costs associated with missing deadlines). Using penalty table  300  according to the present invention, scheduling engine  30  (which may not otherwise have efficient access to accurate information about shortage and inventory costs) is able to determine the effect that scheduling batch  50  at a particular time has on shortage and inventory costs.  
         [0047]    For example, assuming all other criteria considered by batch aggregation engine  20  are equal, engine  20  would typically suggest that batch  50  associated with penalty table  300  be scheduled for a time  330  when the combination of shortage penalty  310  and inventory penalty  320 —the composite penalty  340 —is minimized. Batch aggregation engine  20  outputs the suggested size and time of batch  50  to scheduling engine  30  along with penalty table  300 . Through the use of penalty table  300 , scheduling engine  30  is able to acquire knowledge about the shortage and inventory costs associated with scheduling batch  50  at any time during the time range provided in penalty table  300 . Using this information, scheduling engine  30  can determine the severity (in terms of the effect on inventory and shortage costs) of deviating from the starting time suggested by batch aggregation engine  20  and can determine whether other factors known to scheduling engine  30  (such as the set-up or capacity of the manufacturing equipment, for example) nevertheless warrant moving the starting time of the batch  50  from the suggested starting time to another starting time. Similar determinations as to batch size may be made according to an appropriate penalty table  300 , together with or separate from the determination of the starting time.  
         [0048]    As described above, scheduling engine  30  may include a scheduling system such as the RHYTHM OPTIMAL SCHEDULER produced by i2 TECHNOLOGIES, INC. and described in U.S. Pat. No. 5,319,781. Another suitable scheduling engine  30  is described in U.S. Pat. No. 6,456,996, entitled “Computer Implemented Scheduling System and Process Using Abstract Local Search Technique.” Any suitable scheduling engine  30  may be employed without departing from the intended scope of the present invention.  
         [0049]    In summary, scheduling engine  30  receives suggested batch sizes and starting times as decisions  24  from batch aggregation engine  20 , together with or separate from one or more penalty tables  300  or other suitable feedback  26 . If batch aggregation and scheduling for more than one product is being performed, batch aggregation engine  20  may separately calculate and output the suggested batch sizes and batch starting times for each product. The present invention contemplates batch aggregation engine  20  aggregating multiple batches serially, substantially simultaneously, or in any other suitable manner. Based on this input, scheduling engine  30  determines and schedules actual starting times for batches  50  to be used to meet demands  40 . If batch aggregation and scheduling is to be performed for more than one product type produced on the same equipment (for example, multiple colors of paint), scheduling engine  30  may concurrently schedule the batches for all products types (so as to properly allocate equipment used in manufacturing all such product types). The present invention contemplates scheduling engine  30  scheduling multiple batches serially, substantially simultaneously, or in any other suitable manner.  
         [0050]    The scheduled values for batch starting times (and possibly for batch sizes that were not suggested) are communicated as decisions  34  to batch aggregation engine  20 , together with or separately from one or more penalties or other feedback  36  suitable to provide engine  20  with knowledge relating to the information that scheduling engine  30  used to schedule the batches, and to influence batch aggregation engine accordingly. For example only and not by way of limitation, if scheduling engine  30  left a batch  50  suggested by batch aggregation engine  20  unscheduled because that size of manufacturing equipment is fully utilized, then scheduling engine  30  may output a penalty to batch aggregation engine  20  encouraging the creation of batches  50  in sizes that are under-utilized in the schedule. Other penalties based on the criteria considered by scheduling engine  30  may be communicated to batch aggregation engine  20  in addition to or instead of the example penalties described above, and the penalties may be combined in one or more penalty tables  300  for communication to batch aggregation engine  20 .  
         [0051]    As described above, engines  20  and  30  pass their respective decisions  24  and  34 , respectively, and feedback  26  and  36  (in the form of penalties or otherwise), respectively, to each other in an iterative cycle. With each iteration, the batch aggregation and scheduling solution to a particular series of demands over time horizon  42  will typically converge until a solution is obtained that reflects the relative weights of all the criteria considered by engines  20  and  30 . Furthermore, to encourage convergence, each engine  20  and  30  may increase with each iteration the penalties associated with deviating from its decisions  24  and  34 , respectively, such that after a finite number of iterations a sufficiently optimal solution may become “locked in” and be produced as output  18 .  
         [0052]    Although the present invention has been described with several embodiments, a plethora of changes, substitutions, variations, alterations, and modifications may be suggested to one skilled in the art, and it is intended that the invention encompass all such changes, substitutions, variations, alterations, and modifications as fall within the spirit and scope of the appended claims.