Article Preview
Top1. Introduction
In the late 1950s the evolution of PERT (Project Evaluation and Review Technique) and CPM (Critical Path Method) methods allowed projects to be illustrated by network diagrams where activities are presented by arcs, events are showed by nodes, and the inter-relations between the jobs or activities are described by the network structure. However, project scheduling with these methods deals only with the time issues, without considering the resource restrictions and/or cash flows. Nevertheless, in many actual situations, delays in the activities execution time occur when resources needed by the activities are not available in sufficient amounts during the time interval when they are scheduled to implement. This special problem is known as the ‘‘Resource-Constrained Project Scheduling Problem” (RCPSP) in the literature.
Project scheduling problem (PSP) is made up of activities, resources, precedence relations, and performance measures. In the following, each part is defined.
1.1. Motivation and Significance
Literature survey of this paper indicates that there is a need to dedicate research works to the development of algorithms, approaches and methodologies for net present value maximization of Resource constrained project scheduling problem (RCPSP) considering delay penalties. Therefore, this manuscript focuses on representing three algorithms, which are applicable in this area (according to the literature).
1.2. Activities
Every project is built up of some activities, operations, or tasks. To complete the project successfully, each activity must be executed in one of its several modes. Each mode represents a different way of implementing the activity under consideration. The mode determines the activity duration, measured in number of periods, that signifies the time taken to complete the activity, the resource requirements of various categories and possible cash flows occurring at the start, during the process, or on the completion of the activities.
1.3. Precedence Relations
There are different reasons, which imply that some activities must be finished before others can start, such as technological and environmental restrictions. This is handled by illustrating the project as a directed graph where the activities are presented by a node and the precedence relationships between the activities are represented by directed arcs.
1.4. Resources
There are so many different types of Resources, which will be utilized by the project activities. They are grouped according to categories, types, and their values. Two types of them are called as renewable and nonrenewable resources, which are described as follow:
Renewable resources, are only restricted on a period basis. That is, regardless of the project duration, every renewable resource is available for each single period, such as machines, equipment, and work force.
Nonrenewable resources are constrained over the completely planning horizon, with no limitations within each period. The most common example is the capital budget of a project.
1.5. Representation Issues
Activity-On-Arrow (AOA) and Activity-On-Node (AON) are generally the most common representations of project network, which individually result in an event-based or activity-based illustration. In AOA pattern, events are represented by nodes and activities are illustrated by arrows. Dummy activities are added to keep the precedence relationships and dummy nodes show the start and completion milestones of the project. In the AON pattern, activities and their associated information such as duration, etc. are represented by nodes and the precedence relations are outlined by arrows. In contrast with Gantt-charts, both the AOA and AON representation offer a graphical illustration of the inter-relations among activities. Unlike project scheduling problems with the objective of minimization of project duration, suitable problem representation is an essential issue when the objective is to obtain optimal activity schedules, which maximize the net present value of cash flows. The AOA representation prepares intuitive simplicity and ease in taking the logical flows. In summary, the basic assumption of activity vs. event depiction of the project thus leads to significant varieties in the assumptions for modeling of expenses, payments, and other economical components. Assumptions about these issues have to be clearly mentioned in order that the solution to the model may be interpreted properly.