×

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
First Claim
Patent Images

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.

View all claims
  • 0 Assignments
Timeline View
Assignment View
    ×
    ×