Data processing: generic control systems or specific application – Specific application – apparatus or process – Product assembly or manufacturing
Reexamination Certificate
2003-11-06
2004-12-28
Gandhi, Jayprakash N. (Department: 2125)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Product assembly or manufacturing
C700S103000
Reexamination Certificate
active
06836689
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
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
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 may be reduced or eliminated.
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.
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.
REFERENCES:
patent: 5280425 (1994-01-01), Hogge
patent: 5315521 (1994-05-01), Hanson et al.
patent: 5319781 (1994-06-01), Syswerda
patent: 5408663 (1995-04-01), Miller
patent: 5548518 (1996-08-01), Dietrich et al.
patent: 5715165 (1998-02-01), Luh et al.
patent: 5983195 (1999-11-01), Fierro
patent: 6038540 (2000-03-01), Krist et al.
patent: 6041267 (2000-03-01), Dangat et al.
patent: 6278901 (2001-08-01), Winner et al.
patent: 6321133 (2001-11-01), Smirnov et al.
patent: 6434435 (2002-08-01), Tubel et al.
patent: 6549879 (2003-04-01), Cullick et al.
patent: 6560501 (2003-05-01), Walser et al.
patent: 0 364 090 (1989-08-01), None
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-Albrechts-Universitaet at Kiel, Apr. 1995.
M. H. Bassett,Using detailed scheduling to obtain realistic operating policies for a batch processing facility, Ind. Eng. Chem. Res., 36, pp. 1717-1726, 1997.
R. Z. Rios-Mercado et al.,Heuristics for the flowline problem with setup costs, European Journal of Operational Research 110, pp. 76-98, Aug. 1, 1996.
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.
A. Villa, “Distributed architecture for production planning and control in discrete manufacturing,” Computer Integrated Manufacturing, 0-8186-0888-9/88/0000/0357/$01.00 IEEE, pp. 357-366, May 1988.
Bazaraa, et al., “Seven: The Decomposition Principle,” Linear programming and network flows, John Wiley & Sons, USA, pp. 320-321, XP-002244935, Undated.
PCT, Notification of Transmittal of the International Search Report or the Declaration, 7 pgs., Jul. 15, 2003.
Joslin David E.
Schmidt Craig W.
Walser Joachim Paul
Baker & Botts L.L.P.
Gandhi Jayprakash N.
Garland Steven R.
i2 Technologies US, Inc.
LandOfFree
Collaborative batch aggregation and scheduling in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Collaborative batch aggregation and scheduling in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Collaborative batch aggregation and scheduling in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3316783