Data processing: generic control systems or specific application – Specific application – apparatus or process – Product assembly or manufacturing
Reexamination Certificate
2003-03-20
2004-05-04
Picard, Leo (Department: 2125)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Product assembly or manufacturing
C700S028000, C700S102000
Reexamination Certificate
active
06731998
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to the field of optimization, and more particularly to collaboratively solving an optimization problem using first and second optimization software each having at least partial information concerning the optimization problem.
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 optimization techniques may be reduced or eliminated.
In one embodiment, a method is provided for collaboratively solving an optimization problem using at least first optimization software and second optimization software each having at least partial information concerning the optimization problem. The method includes: (1) determining a solution to a first sub-problem of the optimization problem using the first optimization software based on the at least partial information concerning the optimization problem known to the first optimization software; (2) communicating from the first optimization software to the second optimization software the solution to the first sub-problem and information concerning one or more penalties for deviating from the solution to the first sub-problem; and (3) determining a solution to a second sub-problem of the optimization problem using the second optimization software based on the at least partial information concerning the optimization problem known to the second optimization software, the communicated solution to the first sub-problem, and the communicated information concerning one or more penalties for deviating from the solution to the first sub-problem.
In a more particular embodiment, the first optimization software includes batch aggregation software operable to aggregate product batches according to one or more aggregation criteria and the second optimization software includes scheduling software operable to schedule the aggregated product batches according to one or more scheduling criteria.
Particular embodiments of the present invention may provide one or more technical advantages. For example, according to decisions and associated feedback they communicate to one another, the first and second optimization software may collaborate to provide a suitable solution, such as an aggregation and scheduling solution where the first optimization software includes batch aggregation software and the second optimization software includes scheduling software. Certain particular 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 particular 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 particular embodiments may also reduce the quantity of work-in-process, minimize end-item inventory, and reduce product shortages and late deliveries. Certain particular embodiments may also 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: 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: 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 econmics 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.
A. Drexl et al.,Lot sizing and scheduling—survey and extensions, European Journal of Operational Research 99, pp. 221-235, Dec. 3, 1996.
Y. H. Lee et al.,Scheduling jobs on parallel machines with sequence-dependent setup times, European Journal of Operational Research 100, pp. 464-474, Sep. 27, 1994.
L. J. LeBlanc et al.,Formulating and solving production planning problems, European Journal of Operational Research 112, pp. 54-80, Oct. 1, 1995.
J. F. Goncalves et al.,A hybrid heuristic and linear programming approach to multi-product machine scheduling, European Journal of Operational Research 110, pp. 548-563, Oct. 1, 1996.
K. Aardal,Reformulation of capacitated facility Locations problems: How redundant information can help, Annals of Operations Research 82, pp. 289-308, 1998.
D. E. Joslin et al.,Squeaky-Wheel Optimization, Journal of Artificlal 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 Intel
Joslin David E.
Schmidt Craig W.
Walser Joachim Paul
Bahta Kidest
Baker & Botts L.L.P.
i2 Technologies US, Inc.
Picard Leo
LandOfFree
Collaboratively solving an optimization problem using first... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Collaboratively solving an optimization problem using first..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Collaboratively solving an optimization problem using first... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3195830