Computer implemented scheduling system and process using abstract local search technique

• US 6,456,996 B1
• Filed: 06/04/1999
• Issued: 09/24/2002
• Est. Priority Date: 06/05/1998
• Status: Expired due to Term

• Current Assignee: JDA Software Group Incorporated (Panasonic Holdings Corporation)
• Original Assignee: i2 Technologies US Incorporated (Panasonic Holdings Corporation)
• Inventors: Crawford, James M. Jr., Dalal, Mukesh, Walser, Joachim Paul
• Primary Examiner(s): Trammell, James P.
• Assistant Examiner(s): CHEUNG, MARY DA ZHI WANG
• Application Number:
  US09/325,937
• Time in Patent Office: 1,208 Days
• Field of Search: 707/1-3, 705/8-9, 700/95-97, 709/102-103
• US Class Current: 1/1
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

A method and system for solving constrained optimization problems. An initial abstract solution represents a prioritized set of decisions. The abstract solution is used as the basis for building a concrete solution. The concrete solution is analyzed to determine one or more local moves that represent a re-prioritization of the abstract solution. After a local moves is made, the process begins again with a new abstract solution, that is closer to an optimal solution. This process continues interactively until an optimal solution is reached or approached. The prioritized set of decisions can be implemented as a priority vector or a priority graph.

Claims

1. A local search method of solving an optimization problem having a set of decisions to be made subject to a set of constraints, comprising the steps of:

defining an initial abstract solution, representing a prioritized set of decisions;

building a concrete solution in accordance with said prioritized decisions, subject to said constraints, the concrete solution including all decisions to be made in solving the optimization problem;

analyzing said concrete solution to determine at least one flaw in said concrete solution;

modifying said priorities in response to said analyzing step;

generating at least one local move from said concrete solution, said move representing rectification of said flaw and re-prioritization of said decisions;

re-defining said abstract solution by making said local move; and

interactively repeating said building, analyzing, modifying, generating, and re-defining steps without adding any additional decisions.

2. The method of claim 1, wherein said prioritized set of decisions is implemented with a priority vector having a numerical priority value for each said decision, and wherein said re-prioritization is an update of said numerical values.

3. The method of claim 1, wherein said prioritized set of decisions is implemented with a priority graph representing priority relationships between said decisions, and wherein said re-prioritization is an update of said relationships.

4. The method of claim 1, wherein said constraints are hard constraints and soft constraints, wherein said building step is subject to hard constraints, and wherein said analyzing step is in terms of soft constraints.

5. The method of claim 1, wherein said building step is performed by a greedy solution builder.

6. A local search method of solving a scheduling problem having a set of tasks to be scheduled subject to a set of constraints, comprising the steps of:

defining an initial abstract solution representing a prioritized ordering of said tasks;

building a concrete solution in accordance with said prioritized ordering, subject to said constraints, said concrete solution representing a schedule of all tasks to be scheduled;

analyzing said concrete solution to identify at least one flaw in said concrete solution;

modifying said priorities in response to said analyzing step;

generating at least one local move from said concrete solution, said move representing rectification of said flaw and re-prioritization of said tasks;

re-defining said abstract solution by making said local move; and

interactively repeating said building, analyzing, modifying, generating, and re-defining steps without adding any tasks to be scheduled.

7. The method of claim 6, wherein prioritized set of tasks is implemented with a priority vector having a numerical priority value for each said task, and wherein said re-prioritization is an update of said numerical values.

8. The method of claim 7, wherein said modifying step is performed by increasing priority of a task based on its lateness.

9. The method of claim 7, wherein said initial abstract solution represents an initial prioritized ordering of tasks obtained by associating each tasks with a deadline and assigning higher priorities to tasks with earlier deadlines.

10. The method of claim 6, wherein said prioritized set of tasks is implemented with a priority graph representing priority relationships between said tasks, and wherein said re-prioritization is an update of said relationships.

11. The method of claim 6, wherein said constraints are hard constraints and soft constraints, wherein said building step is subject to hard constraints, and wherein said analyzing step is in terms of soft constraints.

12. The method of claim 6, wherein said building step is performed by a greedy solution builder.

13. The method of claim 6, wherein said analyzing step is performed with critical path analysis techniques.

14. Software for solving an optimization problem having a set of decisions to be made subject to a set of constraints, the software embodied in a computer-readable medium and operable, when executed, to:

define an initial abstract solution, representing a prioritized set of decisions;

build a concrete solution in accordance with said prioritized decisions, subject to said constraints, the concrete solution including all decisions to be made in solving the optimization problem;

analyze said concrete solution to determine at least one flaw in said concrete solution;

modify said priorities in response to said analyzing step;

generate at least one local move from said concrete solution, said move representing rectification of said flaw and re-prioritization of said decisions;

re-define said abstract solution by making said local move; and

interactively repeat said building, analyzing, modifying, generating, and re-defining steps without adding any additional decisions.

15. The software of claim 14, wherein said prioritized set of decisions is implemented with a priority vector having a numerical priority value for each said decision, and wherein said re-prioritization is an update of said numerical values.

16. The software of claim 14, wherein said prioritized set of decisions is implemented with a priority graph representing priority relationships between said decisions, and wherein said re-prioritization is an update of said relationships.

17. The software of claim 14, wherein said constraints are hard constraints and soft constraints, wherein said building, step is subject to hard constraints, and wherein said analyzing step is in terms of soft constraints.

18. Software for solving a scheduling problem having a set of tasks to be scheduled subject to a set of constraints, the software embodied in a computer-readable medium and operable, when executed, to:

define an initial abstract solution representing a prioritized ordering of said tasks;

build a concrete solution in accordance with said prioritized ordering, subject to said constraints, said concrete solution representing a schedule of all tasks to be scheduled;

analyze said concrete solution to identify at least one flaw in said concrete solution;

modify said priorities in response to said analyzing step;

generate at least one local move from said concrete solution, said move representing rectification of said flaw and re-prioritization of said tasks;

re-define said abstract solution by making said local move; and

interactively repeat said building, analyzing, modifying, generating, and re-defining steps without adding any tasks to be scheduled.

19. The software of claim 18, wherein a prioritized set of tasks is implemented with a priority vector having a numerical priority value for each said task, and wherein said re-prioritization is an update of said numerical values.

20. The software of claim 19, wherein the software is operable to modify said priorities by increasing priority of a task based on its lateness.

21. The software of claim 19, wherein said initial abstract solution represents an initial prioritized ordering of tasks obtained by associating each task with a deadline and assigning higher priorities to tasks with earlier deadlines.

22. The software of claim 18, wherein said prioritized set of tasks is implemented with a priority graph representing priority relationships between said tasks, and wherein said re-prioritization is an update of said relationships.

23. The software of claim 18, wherein said constraints are hard constraints and soft constraints, wherein said building step is subject to hard constraints, and wherein said analyzing step is in terms of soft constraints.

24. The software of claim 18, the software is operable to analyze the concrete solution using critical path analysis techniques.