System and method for providing a user-selected best solution to an NP-complete scheduling problem

• US 7,860,814 B1
• Filed: 04/20/2007
• Issued: 12/28/2010
• Est. Priority Date: 04/20/2006
• Status: Active Grant

• Current Assignee: Fredric L. Plotnick
• Original Assignee: Fredric L. Plotnick
• Inventors: Plotnick, Fredric L.
• Primary Examiner(s): Holmes; Michael B.
• Assistant Examiner(s): CHANG, LI WU
• Application Number:
  US11/738,028
• Time in Patent Office: 1,348 Days
• Field of Search: 706/13
• US Class Current: 706/13
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04

Abstract

A method for providing “best” solutions of NP-complete problems. A plurality of algorithms are provided for solving the NP-complete problem, the problem is automatically solved using the provided algorithms and a best solution is selected based on application of predetermined criteria. In one embodiment, scheduling of large or complex projects utilizing limited resources is performed using the method of the invention. Algorithms are provided based on information relating to the constraints of limited resources overlain upon a logic network of restraints between events and activities in a sequence to model the real world. The generated rule sets can be applied to generate multiple schedules from which a particular schedule may be selected. A system for implementation of the method using a computer and a computer program is also provided.

Claims

1. A method for handling an NP-complete problem, comprising the steps of:

(a) generating a resource allocation algorithm yielding a single schedule for performance of interrelated activities which is consistent with restraints on a sequence of performance of the interrelated activities employing a priority rule set to provide a method of prioritization of resource allocation for performance of the interrelated activities consistent with the restraints on the sequence of performance of the interrelated activities;

(b) generating another resource allocation algorithm yielding a single schedule for performance of interrelated activities which is consistent with restraints on the sequence of performance of the interrelated activities employing a different priority rule set than was employed in a previous step of generating a resource allocation algorithm in order to provide a different method of prioritization of resource allocation for performance of the interrelated activities consistent with the restraints on the sequence of performance of the interrelated activities;

(c) repeating step (b), if necessary, until a desired number of resource allocation algorithms has been generated;

(d) storing the generated resource allocation algorithms in a computer prior to performing steps (e)-(g);

(e) defining the NP-complete problem in the computer as a problem of scheduling a plurality of interrelated activities subject to a plurality of restraints on a sequence of performance of the activities;

(f) solving, on the computer, the NP-complete problem defined by said activities interrelationships between said activities and said restraints using the plurality of generated resource allocation algorithms stored in said computer;

said solving step solving each of said generated resource allocation algorithms once to generate a single schedule for performance of said interrelated activities which is consistent with said restraints on the sequence of performance of the activities from each of said generated resource allocation algorithms to thereby provide a number of schedules for performance of said interrelated activities which is consistent with said restraints on the sequence of performance of the activities equal to the number of resource allocation algorithms,

(g) selecting a best schedule for performance of said interrelated activities from among the plurality of schedules for performance of said interrelated activities provided by said solving step based on application of user-selected criteria for determining a best schedule for performance of said interrelated activities.

2. The method of claim 1, wherein at least one said priority rule set is based upon a relationship between an activity and one or more restraints on the sequence of performance for a preceding or succeeding activity.

5. The method of claim 1, wherein the user-selected criteria are selected from the group consisting of cost, completion time, efficient use of resources and combinations thereof.

10. The method of claim 1, wherein one said priority rule set determines priority of activities based on allocated resources.

13. The method of claim 1, wherein one said priority rule set determines priority of activities based on a duration of one or more activities.

3. A system for solving an NP-complete problem for scheduling a plurality of interrelated activities subject to a plurality restraints on a sequence of performance of the activities, comprising:

a computer;

a program stored on said computer, wherein said program, when executed, performs the steps of;

(a) generating a resource allocation algorithm yielding a single schedule for performance of interrelated activities which is consistent with restraints on the sequence of performance of the interrelated activities employing a priority rule set to provide a method of prioritization of resource allocation for performance of the interrelated activities consistent with the restraints on the sequence of performance of the interrelated activities;

(b) generating another resource allocation algorithm yielding a single schedule for performance of interrelated activities which is consistent with restraints on the sequence of performance of the interrelated activities employed a different priority rule set than was employed in a previous step of generating a resource allocation algorithm in order to provide a different method of prioritization of resource allocation for performance of the interrelated activities consistent with the restraints on the sequence of performance of the interrelated activities;

(c) repeating step (b), if necessary, until a desired number of resource allocation algorithms has been generated;

(d) storing the generated resource allocation algorithms prior to performing steps (e)-(g);

(e) receiving said activities, interrelationships between said activities and one or more restraints on a sequence of performance of the activities;

(f) generating a number of schedules for performance of said interrelated activities, equal to the number of generated resource allocation algorithms for solving the NP-complete problem by solving each of said generated resource allocation algorithms using said received restraints on the sequence of performance of the interrelated activities to provide one schedule for performance of said interrelated activities from each of said generated resource allocation algorithms; and

(g) selecting a best schedule for performance of said interrelated activities from among the generated schedules for performance of said interrelated activities based upon application of user-selected criteria for determining a best schedule for performance of said interrelated activities.

4. The system of claim 3, wherein at least one said priority rule set is based upon a relationship between an activity and one or more restraints on the sequence of performance for a preceding or succeeding activity.

6. The system of claim 3, wherein the user-selected criteria are selected from the group consisting of cost, completion time, efficient use of resources and combinations thereof.

11. The system of claim 3, wherein one said priority rule set determines priority of activities based on allocated resources.

14. The system of claim 3, wherein one said priority rule set determines priority of activities a duration of one or more activities.

7. A method for generating and displaying a path or project schedule involving an NP-complete problem for scheduling, comprising the steps of:

(a) generating a resource allocation algorithm yielding a single schedule for performance of interrelated activities which is consistent with restraints on a sequence of performance of the interrelated activities employed a priority rule set to provide a method of prioritization of resource allocation for performance of the interrelated activities consistent with the restraints on the sequence of performance of the interrelated activities;

(b) generating another resource allocation algorithm yielding a single schedule for performance of interrelated activities which is consistent with restraints on the sequence of performance of the interrelated activities employing a different priority rule set than was employed in a previous step of generating a resource allocation algorithm in order to provide a different method of prioritization of resource allocation for performance of the interrelated activities consistent with the restraints on the sequence of performance of the interrelated activities;

(c) repeating step (b), if necessary, until a desired number of resource allocation algorithms has been generated;

(d) storing the generated resource allocation algorithms in a computer prior to performing steps (e)-(h);

(e) defining the NP-complete problem in the computer as a problem of scheduling a plurality of interrelated activities subject to a plurality of restraints on a sequence of performance of the activities;

(f) solving, on the computer, the NP-complete problem defined by said activities, interrelationships between said activities and said restraints using the plurality of generated resource allocation algorithms stored in the computer to provide a plurality of solutions to the NP-complete problem in the form of paths or project schedules for performance of said interrelated activities,

(g) selecting a best path or project schedule for performance of said interrelated activities from among the paths or project schedules for performance of said interrelated activities provided by said solving step based on application of user-selected criteria for determining a best path or project schedule for performance of said interrelated activities, and

(h) displaying the selected path or project schedule for performance of said interrelated activities.

8. The method of claim 7, wherein said priority rule set is based upon a relationship between an activity and one or more restraints on the sequence of performance for a preceding or succeeding activity.

9. The method of claim 7, wherein the user-selected criteria are selected from the group consisting of cost, completion time, efficient use of resources and combinations thereof.

12. The method of claim 7, wherein one said priority rule set determines priority of activities based on allocated resources.

15. The method of claim 7, one said priority rule set determines priority of activities a duration of one or more activities.