Method and apparatus for plan generation

• US 20050159994A1
• Filed: 07/09/2004
• Published: 07/21/2005
• Est. Priority Date: 07/11/2003
• Status: Abandoned Application

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Inventors: Parish, Michael E., Polyak Goykhberg, Ella, Huddleston, David E., Duan, Baofu, Pao, Yoh-Han, Meng, Zhuo, Cass, Ronald J.
• Application Number:
  US10/887,654
• Publication Number:
  US 20050159994A1
• Time in Patent Office: Days
• US Class Current: 705/10
• 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
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/0637 Strategic management or analysis, e.g. setting a goal or target of an organisation; Planning actions based on goals; Analysis or evaluation of effectiveness of goals

Abstract

A method for plan generation is provided. One or more initial plans are generated and evaluated to determine quality scores for the plans. One or more of the plans is selected according to the quality scores and modified to generate modified plans. The modified plans are evaluated to determine updated quality scores for the modified plans. Selection, modification and evaluation of modified plans are repeated until one of the modified plans is satisfactory.

Claims

1. A method for plan generation, comprising:

(a) generating one or more initial plans;

(b) evaluating the plans to determine quality scores for the plans;

(c) selecting one or more of the plans according to the quality scores and modifying the selected plans to generate modified plans;

(d) evaluating the modified plans to determine updated quality scores for the modified plans; and

(e) determining whether at least one of the modified plans is satisfactory.

2. The method of claim 1, wherein validity rules are used to generate the initial plans.

3. The method of claim 1, wherein at least one of the initial plans is generated by applying heuristics.

4. The method of claim 1, wherein at least one of the initial plans is generated randomly.

5. The method of claim 1 further comprising assessing whether the modified plans are valid plans.

6. The method of claim 1, wherein at least one of the modified plans is generated by applying evolution rules.

7. The method of claim 1, wherein a parameter corresponding to an amount of change is applied to generate at least one of the modified plans.

8. The method of claim 1, wherein at least one of the modified plans is generated using Guided Evolutionary Simulated Annealing.

9. The method of claim 1 further comprising repeating (c) through (e) until at least one of the modified plans is satisfactory.

10. The method of claim 1, wherein a modified plan is satisfactory if the quality score of the modified plan is a satisfactory value.

11. The method of claim 1, wherein a modified plan is satisfactory if a quality score of the modified plan converges.

21. A computer system, comprising:

a processor; and

a program storage device readable by the computer system, tangibly embodying a program of instructions executable by the processor to perform the method claimed in claim 1.

22. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method claimed in claim 1.

23. A computer data signal transmitted in one or more segments in a transmission medium which embodies instructions executable by a computer to perform the method claimed in claim 1.

12. An apparatus for plan generation, comprising:

a planning module adapted to generate one or more plans, evaluate the plans to determine quality scores for the respective plans, select one of the plans based on the quality scores, and modify the selected plan to generate one or more modified plans; and

an optimization module adapted to drive the planning module to develop a satisfactory plan.

13. The apparatus of claim 12, wherein the planning module includes a plan generation submodule for generating valid plans.

14. The apparatus of claim 13, wherein the plan generation submodule generates the valid plans by applying heuristics.

15. The apparatus of claim 13, wherein the plan generation submodule generates the valid plans by applying validity rules.

16. The apparatus of claim 12, wherein the planning module includes a plan evolution submodule for modifying the selected plan to generate the one or more modified plans.

17. The apparatus of claim 16, wherein the plan evolution submodule applies evolution rules to generate the modified plans.

18. The apparatus of claim 16, wherein the plan evolution submodule applies a parameter corresponding to an amount of change to generate the modified plans.

19. The apparatus of claim 12, wherein the planning module includes a plan scoring submodule for evaluating a plan to determine a quality score for the plan.

20. The apparatus of claim 12, wherein the satisfactory plan has a satisfactory associated quality score.