Optimization prediction for industrial processes

• US 6,490,572 B2
• Filed: 05/15/1998
• Issued: 12/03/2002
• Est. Priority Date: 05/15/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Murthy, Seshashayee Sankarshana, Wu, Frederick Yung-Fung, Akkiraju, Rama Kalyani Tirumala, Keskinocak, Pinar, Rachlin, John Nathan, Dietrich, Brenda Lynn
• Primary Examiner(s): Davis, George B.
• Application Number:
  US09/080,320
• Publication Number:
  US 20010013027A1
• Time in Patent Office: 1,663 Days
• Field of Search: 706/21, 706/13, 706/19
• US Class Current: 706/19
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

Abstract

Prediction methods that anticipate the outcome of a detailed optimization step are used in lieu of or in conjunction with actual optimization to improve response time and reduce required computational resources for optimization problems having a hierarchical structure. Decomposition of the optimization problem into sub-problems and sub-sub-problems is, itself, an optimization process which is iteratively performed while preferably guided by prediction of the quality of solutions to the problems into which the “master” optimization problem may be decomposed. Prediction also reduces the requirements for computational resources and allows more decompositions to be examined within the available time in order to arrive at a more nearly optimal decomposition as well as a more nearly optimal solution. Prediction is selectively used when it is determined that such a benefit is probable.

Claims

1. A computer implemented scheduling optimization method for solving a scheduling problem in an industrial or manufacturing environment comprising the steps of:

(a) decomposing said scheduling optimization problem into a first plurality of sub-problems for the purpose of creating smaller, simpler problems that can be more easily evaluated and/or solved, the method of decomposition being dependent on a problem domain and problem parameters,

(b) predicting an evaluation of a solution to at least one sub-problem creating at least one predicted evaluation for a sub-problem,

(c) evaluating a composed solution of said scheduling optimization problem based on at least one of an evaluation of a solution and a predicted evaluation for each sub-problem, said composed solution including at least one said predicted evaluation,

(d) repetitively performing steps (a), (b) and (c), each time forming a new plurality of sub-problems wherein at least one of said sub-problems of said new plurality of sub-problems differs from sub-problems of previously formed pluralities of sub-problems,

(e) selecting, based on at least one of an evaluation of a solution and a predicted evaluation for each sub-problem, a decomposition for solution of said scheduling optimization problem, and

(f) optimizing a schedule for an industrial or manufacturing process in accordance with a solution of a decomposition of said scheduling optimization problem.

2. A method as recited in claim 1, including the further step of solving each sub-problem into which said optimization problem is decomposed by said decomposing step or a repetition of said decomposing step.

3. A method as recited in claim 1, wherein said repetition of said decomposing step to form a new plurality of sub-problems is based on an evaluation which identifies a sub-problem for which a solution is predicted that is inconsistent with a solution to said optimization problem.

4. A method as recited in claim 1, wherein said repetition of said decomposing step to form a new plurality of sub-problems is based on an evaluation of a sub-problem of said first plurality of sub-problems.

5. A method as recited in claim 1, wherein said repetition of said decomposing step to form a new plurality of sub-problems is based on a random modification of said decomposition into said first plurality of sub-problems.

6. A method as recited in claim 1 wherein a prediction method employed in said step of predicting an evaluation includes a nearest neighbor method.

7. A method as recited in claim 1 wherein a prediction method employed in said step of predicting an evaluation includes a neural-network method.

8. A method as recited in claim 1 further including the step of combining two or more prediction methods into a single prediction method for enhanced performance or accuracy.

9. A method as recited in claim 1, further including a step of detailed optimization to validate classifier predictions.

10. A method as recited in claim 1 wherein at least one sub-problem corresponds to a downstream process in the context of a scheduling task.

11. A method as recited in claim 1 wherein at least one sub-problem corresponds to an upstream process in the context of a scheduling task.