Data processing: generic control systems or specific application – Specific application – apparatus or process – Product assembly or manufacturing
Reexamination Certificate
2000-03-07
2003-05-06
Picard, Leo (Department: 2125)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Product assembly or manufacturing
C700S106000, C705S002000
Reexamination Certificate
active
06560501
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to the field of manufacturing planning and optimization, and more particularly to a system and method for collaborative batch aggregation and scheduling.
BACKGROUND OF THE INVENTION
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.
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
According to the present invention, disadvantages and problems associated with previous batch aggregation and scheduling techniques have been substantially reduced or eliminated.
According to one embodiment of the present invention, a computer-based system for aggregating and scheduling product batches includes a batch aggregation engine that allocates one or more product demands to one or more product batches having suggested sizes and suggested starting times. The batch aggregation engine communicates to a scheduling engine the suggested batch sizes, the suggested starting times, and feedback relating to the suggested sizes and suggested starting times to assist the scheduling engine in scheduling a start time for one or more product batches. In a more particular embodiment, the feedback includes one or more penalties associated with deviating from at least one of the suggested sizes or at least one of the suggested starting times.
In another embodiment of the present invention, the system also includes a scheduling engine coupled to the batch aggregation engine that receives the suggested sizes, suggested starting times, and feedback from the batch aggregation engine. The scheduling engine schedules a starting time for one or more of the batches according to the suggested sizes, suggested starting times, and feedback received from the batch aggregation engine. The scheduling engine also communicates the scheduled starting times and feedback relating to the scheduled starting times to the batch aggregation engine to assist the batch aggregation engine in allocating the demands to the batches.
In a more particular embodiment, the feedback includes one or more penalties associated with deviating from at least one of the scheduled starting times.
In yet another embodiment of the present invention, the batch aggregation engine and the scheduling engine communicate their respective outputs to each other in an iterative cycle until they have collaboratively reached a sufficiently optimal batch aggregation and scheduling solution or until a predetermined number of iterations has been reached.
In yet another embodiment of the present invention, a method is provided for collaboratively solving an optimization problem using a plurality of optimization engines, each engine having at least partial information about the optimization problem, the partial information relating to one of a plurality of sub-problems of the optimization problem. The method includes determining a solution to a first sub-problem using a first optimization engine, where the solution is based on the partial information known to the first optimization engine. The method further includes communicating the solution to the first sub-problem and one or more penalties relating to deviating from the solution from the first optimization engine to a second optimization engine. The method also includes determining a solution to a second sub-problem using the second optimization engine, where the solution is based on the partial information known to the second optimization engine and determined according to the solution and penalties received from the first optimization engine.
The systems and methods of the present invention provide a number of important technical advantages. The present invention allows 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. According to the decisions and associated feedback they communicate to one another, the batch aggregation engine and scheduling engine collaborate to provide a suitable aggregation and scheduling solution. The present invention is capable of aggregating batches of variable size across multiple production stages and computing material flows between these stages. By allowing for variable batch sizes, the present invention enables the use of a variety of equipment sizes in the manufacturing process and optimizes the use of each of these equipment sizes. The present invention also reduces the quantity of work-in-process, minimizes end-item inventory, and reduces product shortages and late deliveries. The present invention may also be used to optimize other manufacturing and supply chain planning processes, according to particular needs. Other important technical advantages are readily apparent to those skilled in the art.
REFERENCES:
patent: 5319781 (1994-06-01), Syswerda
patent: 5548518 (1996-08-01), Dietrich et al.
patent: 5983195 (1999-11-01), Fierro
patent: 6041267 (2000-03-01), Dangat et al.
patent: 6278901 (2001-08-01), Winner et al.
patent: 6321133 (2001-11-01), Smirnov et al.
D. E. Joslin et al.,Squeaky Wheel Optimization,Journal of Artificial Intelligence Research, vol. 10, pp. 353-373, Aug. 1998.
J. M. Crawford et al.,Abstract Local Search,In Proceedings of the AIPS-98 Workshop on Planning as Combinatorial Search (held in conjunction with the Fourth International Conference on Artificial Intelligence Planning Systems, AIPS-98), Pittsburgh, 1998.
J. M. Pinto et al., “STBS: A Continuous Time MILP Optimization for Short Term Scheduling of Batch Plants,” Computers and Chemical Engineering, vol. 22, pp. 1297-1308, Dec. 17, 1997.
S. C. K. Chu,A mathematical programming approach towards optimized master production scheduling,Int. Journal of Production Economics 38 (1995), pp. 269-279, Feb. 15, 1994.
S. K. Das et al.,An integrated approach to solving the master aggregate scheduling problem,Int. Journal of Production economics 34 (1994), pp. 167-178, May 2, 1990.
W. G. M. Rutten et al.,Balancing stocks, flexible recipe costs and high service level requirements in a batch process industry: A study of a small scale model,European Journal of Operational Research 110 (1998), pp. 626-642, Feb. 20, 1996.
C. Jordan et al.,Discrete lotsizing and scheduling by batch sequencing,Working Paper, Christian-Albrec
Joslin David E.
Schmidt Craig W.
Walser Joachim Paul
Bahta Kidest
Baker & Botts L.L.P.
i2 Technologies US, Inc.
LandOfFree
System and method for collaborative batch aggregation and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for collaborative batch aggregation and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for collaborative batch aggregation and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3061183