Method and apparatus for resource constraint scheduling
First Claim
1. In a computer system comprising a central processing unit, a display monitor comprising a matrix of pixels and a memory, said memory for storing a project network comprising a plurality of activities to be performed, said activities being scheduled in order of precedence, each activity requiring zero or more resources to perform the activity, a method for probabilistic resource constrained scheduling of activities in the project network comprising the steps of:
- receiving electrical signals which define a list of activities, comprising estimated parameters of probability distributions on activity durations, the resources each activity will require, and a confidence factor;
storing said list of activities in said memory;
establishing a precedence arc between an activity and each predecessor activity which must be performed before the activity can be performed;
manipulating the data by means of electrical signals in said memory for creating a deterministic unconstrained schedule of activities in logical order comprising the precedence arcs identifying the predecessor activities, calculated slack times and unconstrained start and finish times for each activity comprising the steps of;
(1) assigning all activities with no predecessor activities to a Schedulable list and all other activities to an Unschedulable list;
(2) iteratively selecting from the Schedulable list each activity to be scheduled, taking into account resource constraints as necessary to provide an accurate schedule of activities in a project network, each iteration comprising the steps of;
selecting a current activity from the Schedulable list, said current activity being the activity having the least amount of slack time,determining if the resources required by the current activity are available, and therefore the current activity is resource constrainable,if the resource is not available, adding a resource arc from the current activity to the scheduled activity which must complete utilization of the resource before the resource is available for the current activity to use; and
scheduling the current activity and moving the activity to a Scheduled list;
repeating steps (1) and (2) until all activities are scheduled;
calculating the start time of each activity preserving the confidence factor of the project network based upon means, variances, and correlation coefficients of cumulative duration through all incoming activities as identified by the resource and precedence arcs;
calculating the end time of each activity based on the supplied parameters of a probability distribution on activity durations and the confidence factor; and
generating an electrical signal to actuate the pixels on said display monitor for displaying said schedule of activities,whereby the uncertainty of activity durations is taken into account and the schedule is resource feasible within the prescribed confidence level.
0 Assignments
0 Petitions
Accused Products
Abstract
Constrained resource allocation techniques are implemented with a digital computer due to its improved speed and graphics capability. These techniques allow for rapid resource constrained scheduling when given a precedence ordered list of activities. Resources are allocated to activities in order of highest priority with all precedence constraints being taken into account. Resources are allocated in such a manner that preserves the integrity of the random variables associated with start and finish times of activities. Activity durations and start/finish expected values and variances are adjusted to account for shortfalls occurring prior to an activity'"'"'s start time and between an activity'"'"'s start and finish times. The result is a schedule of start and finish times for each activity that is resource feasible and achievable within a prescribed confidence level.
105 Citations
24 Claims
-
1. In a computer system comprising a central processing unit, a display monitor comprising a matrix of pixels and a memory, said memory for storing a project network comprising a plurality of activities to be performed, said activities being scheduled in order of precedence, each activity requiring zero or more resources to perform the activity, a method for probabilistic resource constrained scheduling of activities in the project network comprising the steps of:
-
receiving electrical signals which define a list of activities, comprising estimated parameters of probability distributions on activity durations, the resources each activity will require, and a confidence factor; storing said list of activities in said memory; establishing a precedence arc between an activity and each predecessor activity which must be performed before the activity can be performed; manipulating the data by means of electrical signals in said memory for creating a deterministic unconstrained schedule of activities in logical order comprising the precedence arcs identifying the predecessor activities, calculated slack times and unconstrained start and finish times for each activity comprising the steps of; (1) assigning all activities with no predecessor activities to a Schedulable list and all other activities to an Unschedulable list; (2) iteratively selecting from the Schedulable list each activity to be scheduled, taking into account resource constraints as necessary to provide an accurate schedule of activities in a project network, each iteration comprising the steps of; selecting a current activity from the Schedulable list, said current activity being the activity having the least amount of slack time, determining if the resources required by the current activity are available, and therefore the current activity is resource constrainable, if the resource is not available, adding a resource arc from the current activity to the scheduled activity which must complete utilization of the resource before the resource is available for the current activity to use; and scheduling the current activity and moving the activity to a Scheduled list; repeating steps (1) and (2) until all activities are scheduled; calculating the start time of each activity preserving the confidence factor of the project network based upon means, variances, and correlation coefficients of cumulative duration through all incoming activities as identified by the resource and precedence arcs; calculating the end time of each activity based on the supplied parameters of a probability distribution on activity durations and the confidence factor; and generating an electrical signal to actuate the pixels on said display monitor for displaying said schedule of activities, whereby the uncertainty of activity durations is taken into account and the schedule is resource feasible within the prescribed confidence level. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A computer system for resource constrained scheduling of activities in a project network, said computer system comprising a central processing unit, a display monitor comprising a matrix of pixels and a memory, said activities being scheduled in order of precedence, each activity requiring zero or more resources to perform the activity, said computer system comprising:
-
input means for receiving a list of defined activities, the resources required by each activity and any predecessor activities which must be performed before the activity can be performed, said list of defined activities and said resources being stored in said memory for manipulation by electrical signals under the control at said central processing unit; means for defining an Unschedulable list in said memory comprising those activities having predecessor activities not yet scheduled; means for defining a Schedulable list in said memory comprising those activities with scheduled predecessor activities; means for defining a Scheduled list in said memory for those activities which are scheduled; means for iteratively scheduling activities comprising; means for manipulating activities in said memory among the unschedulable, schedulable and scheduled lists, whereby a current activity is moved from the Unschedulable to the Schedulable list when the current activity has no predecessor activities or the current activity has predecessor activities which have been scheduled; the current activity is moved from the Schedulable list to the Scheduled list in an order according to a selection mechanism, said current activity is moved once it is determined that the resources required by the current activity are available and the current activity is resource constrained; if the resources required by the current activity are not available, means for adding a resource arc from the current activity to the scheduled activity which must complete utilization of the resource before the resource is available for the selected activity to use; calculating means for determining the start time of each activity scheduled preserving the confidence factor of the project network and based upon the incoming activities as identified by the resource and precedence arcs; means for calculating the finish time of each activity based on the parameters of a probability distribution on activity durations; and means for generating an electrical signal to actuate the pixels on said display monitor for displaying the schedule of activities, whereby the uncertainty of activity durations is taken into account and the schedule is resource constrained and feasible. - View Dependent Claims (10, 11, 12)
-
-
13. In a computer system comprising a central processing unit (CPU), an input/output (I/O) means coupled to said CPU for providing a communication interface, a memory means coupled to said I/O means for storing instructions and computer dam, data input means coupled to said I/O means for providing data input and data output to interface with a computer user, and a display device coupled to said I/O means, said display device comprising a matrix of pixels for displaying results, said computer system determining an optimal project network for allocating a number of resources among a number of activities, said memory for storing data representations of the activities and data representations of the resources, said activities being scheduled in order of precedence, a method for probabilistic resource constrained scheduling of activities comprising the steps of:
-
receiving electrical signals through said data input means which define the data representation of said activities and said resources, wherein the data representation of each of said activities includes estimated parameters of probability distributions on each of said activities durations, the resources required, and confidence factors; storing said data representations of said activities and said resources in said memory; examining the data representation of each activity and establishing data in said memory corresponding to a precedence are between the data representation of an activity and the data representation of each activity which must be performed before the activity Can be performed; manipulating the data in said memory by means of electrical signals provided to said memory for creating a deterministic unconstrained schedule of activities in logical order comprising the precedence arcs data identifying predecessor activities, calculated slack times and unconstrained start and finish times for each activity Comprising the steps of; (1) assigning the data representation of all activities with no predecessor activities to a Schedulable list in said memory and the data representation of all other activities to an Unschedulable list in said memory; (2) iteratively selecting from the Schedulable list in said memory the data representation of each activity to be scheduled, taking into account resource constraints as necessary to provide an accurate schedule of activities in the project network, each iteration comprising the steps of; selecting a data representation of a current activity from the Schedulable list in said memory, said current activity being the activity having the least amount of slack time, determining, from said data representation stored in said memory, if the resources required by the current activity are available, and therefore the current activity is resource constrainable, if a resource is not available, establishing data in said memory corresponding to a resource arc from the current activity to the scheduled activity which must complete utilization of the resource before the resource is available for the current activity to use; and scheduling the current activity and moving the data representation of the activity to a Scheduled list in said memory; repeating steps (1) and (2) until all activities are scheduled; calculating, from said data representation stored in said memory, the start time of each activity, preserving the confidence factor of the project network based upon means, variances, and correlation coefficients of cumulative duration through all incoming activities as identified by the resource and precedence arcs data; calculating, from said data representation stored in said memory, the end time of each activity based on the supplied parameters of a probability distribution on activity durations and the confidence factor; and generating an electrical signal to actuate the pixels on said display device for displaying said schedule of activities, whereby the uncertainty of activity durations is taken into account and the schedule is resource feasible within the prescribed confidence level. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
-
-
21. A computer system for resource constrained scheduling of activities in a project network, said computer system comprising a central processing unit (CPU), an input/output (I/O) means coupled to said CPU for providing a communication interface, a memory means couple to said I/O means for storing instructions and computer data, an data input means coupled to said I/O means for providing data input and data output to interface with a computer user, and a display device coupled to said I/O means, said display device comprising a matrix of pixels which can be selectively activated by providing electrical signals, said activities being scheduled in order of precedence, each activity requiring zero or more resources to perform the activity, said computer system comprising:
-
data input means for receiving data representations of the activities and the data representations of the resources required by each activity and any predecessor activities which must be performed before the activity Can be performed, said data representations being stored in said memory for manipulation by electrical signals under the control of said CPU; means for defining an Unschedulable list in said memory comprising those activities having predecessor activities not yet scheduled; means for defining a Schedulable list in said memory comprising those activities with scheduled predecessor activities; means for defining a Scheduled list in said memory for those activities which are scheduled; means for iteratively scheduling activities comprising; means for manipulating the data representations stored in said memory among the unschedulable, schedulable and scheduled lists, wherein data representation of a current activity is moved from the Unschedulable list to the Schedulable list when the current activity has no predecessor activities or the current activity has predecessor activities which have been scheduled; the data representation of the current activity is moved from the Schedulable list to the Scheduled list in an order according to a selection mechanism, said data representation of the current activity is moved once it is determined that the resources required by the current activity are available and the current activity is resource constrained; if the resources required by the current activity are not available, means for establishing in said memory a data representation of a resource arc from the current activity to the scheduled activity which must complete utilization of the resource before the resource is available for the selected activity to use; means for calculating, from said data representation stored in said memory, the start time of each activity scheduled, preserving the confidence factor of the project network and based upon the incoming activities as identified by the resource and precedence arcs; means for calculating, from said data representation stored in said memory, the finish time of each activity based on the parameters of a probability distribution on activity durations; and means for generating an electrical signal to activate the pixels on said display device for displaying the schedule of activities, whereby the uncertainty of activity durations is taken into account and the schedule is resource constrained and feasible. - View Dependent Claims (22, 23, 24)
-
Specification