Resource-constrained project scheduling (RCPSP)
A
heuristic procedure for solving the "Resource-Constrained
Project Scheduling Problem " (RCPSP with a renewable resource
and a single mode) is used. A formal description of the procedure is described
by Kolisch/Drexl (1996), p. 38.
The objective of the model is the minimization of the makespan.
Opposite to the infinite loading problem, offset times between tasks are not
considered.
The procedure is based on a dynamic partitioning of the set
of tasks into the subsets "Completed"
(Cn), "Active" (An),
"Assignable" (Dn). Beginning with a planning period t=0, all
assignable tasks are scheduled on the resources as early as possible. After
scheduling all assignable tasks with respect to the actual planning period t
is increased and so forth. The set of assignable tasks can be sorted according
to the following priority rules:
-
Shortest processing time
- Number of immediate successors
- Total slack time
- Capacity requirement
- Rank positional weight
- Total number of successors
The project is defined with the help of the graph editor:
The procedure is run with a single click. The complete protocol of all calculations
is shown in the lower right list. Click on this list with the left mouse button
to copy the protocol into the clipboard.
You may wish to display a gantt chart which
may be printed:
You can also display a resource utilisation
graph which
may be printed:
The following symbols are also used in the
infinite scheduling module:
| i |
index of tasks
|
| D(i) |
duration of task i |
| FAZ(i) |
earliest start time of task i |
| FEZ(i) |
earliest finish time of task i |
| SAZ(i) |
lastest start time of task i |
| SEZ(i) |
latest finish time of task i |
| GP(i) |
slack time of task i |
Additional symbols with respect to the resources:
| r |
index of resources |
| r(i) |
number of resource used by task i |
| k(i,r) |
resource requirement of resource r by task i |
| Kap(r) |
(renewable capacity
of resource k |
| t |
current planning
time |
| An |
set of tasks in
process at time t |
| Cn |
set of tasks
completed at time t |
| Dn |
set of tasks
available for starting at time t |
Assumptions:
- deterministisc processing times
- renewable resources
Literature:
- Kolisch, R. and A. Drexl, Adaptive Search for Solving
Hard Project Scheduling Problems, in: Naval Research Logistics 43(1996), pp.
23-40
|
