INTRODUCTION
The general ResourceConstrained Project Scheduling Problem (RCPSP) is
considered as follows. A project consists of a set of activities which
have to be processed. The activities are interrelated by two kinds of
constraints. First, precedence constraints force each activity not to
be started before all its immediate predecessor activities have been finished.
Second, performing the activities requires renewable resources with deterministic
limited capacities at any decision point. Where resources are renewable,
activity durations are resource driven and the availability of each resource
is renewed at each period of the planning horizon (AlvarezValdes et
al., 2006). The activity durations are independent continuous random
variables; preemption is not allowed. The objective of the problem is
to find the feasible sequence for project activities such that makespan
of project be minimized. Blazewicz et al. (1983) have presented
that this problem is a generalization of the classical job shop scheduling
problem and belongs to the class of NPhard optimization problems. Therefore,
heuristic solution procedures are indispensable when solving large problem
instances as they usually appear in practical cases.
A large number of different heuristic algorithms have been suggested
in the literature (Herroelen and Leus, 2005). These heuristic procedures
have been used very widely in practice (Kolisch and Hartmann, 1998; Bouleimen
and Lecocq, 2003; Mika et al., 2005; Kolisch and Hartmann, 2006).
A common feature of all heuristics is that they provide a criterion for
prioritization. Accordingly, in attempt to develop perfect algorithms
for scheduling activities under resource constraints, theorists have designed
various values to determine which activity will get the resources and
which activity will be delayed. The limited resource project scheduling
problem falls into a category of mathematical problems known as combinatorial
problems. Analytical methods such as mathematical programming have not
proven very successful on these combinatorial problems. Instead, various
heuristicbased procedures have been developed (Liess and Michelon, 2008).
Heuristics may not always produce the best solution in every case, but
their usefulness in finding good solutions with a minimum of effort is
wellknown, based on experience and research studies. The heuristic procedures
broadly fall into two categories, namely constructive heuristics and improvement
heuristics (Sprecher et al., 1995). Constructive heuristics consist
of two major components, namely the scheduling scheme and the priority
rule. The scheduling scheme determines the way in which a feasible schedule
is constructed by assigning starting times to the different activities.
The priority rule determines the activity that is selected next during
the heuristic search process.
In case of ties, one or several tie breaking rules have to be employed.
Many researchers have investigated the resource allocation problem; Brucker
et al. (1999) and Kolisch and Padman (2001) present extensive overviews
of resource allocation research. Priority rules can be classified in two
major groups, according to different criteria employed for the type of
information required to calculate a value. The first group is network/resource
based rules which make benefit the information contained in the network
and information about the resource. The second group is the rules dealing
with the type of information required for the networks. The efficiency
of priority rules heuristic for project scheduling under resource constraints
has been described in the literature (Demeulemeester and Herroelen, 2002).
We have used this efficiency for considered problem.
We developed a new constructive heuristic rule constructed from two wellknown
priority rules, Time Criticality Index (T_{CI}) and Resource Criticality
Index (R_{CI}). According to the classification scheme for project
scheduling from Herroelen et al. (1998) we use a regular performance
measure, in particular the makespan. That is to say, the objective is
to minimize the project makespan. Instead of analyzing the makespan values,
we analyze it expressed in the percentage increase with respect to the
best possible solution project duration. Thus, this is a measurement of
efficiency, given that we compared the performance of the new constructive
heuristic rule with the best possible solution.
PROBLEM STATEMENT
The ResourceConstrained Project Scheduling Problem (RCPSP) can be stated
as follows:
Project network G (N, A) is shown as PERT type network with an ActivityOnArc
(AOA) format, the set of arcs A is used to represent the n activities
(numbered from 1 to n) and a set of nodes N to represent the precedence
relations between activities, which are assumed to be finishstart relations
with a minimal timelag of zero. Activities durations are independent
continuous random variables with given distribution functions which require
only renewable resource. The amount of limited available resource is deterministic
and allocation is performed discretely. Preemption is not allowed. We
use a regular performance measure, in particular the makespan. That is
to say, the objective is to minimize the project duration.
According to the above, the considered model is defined as follows:
where:
PROPOSED NEW CONSTRUCTIVE HEURISTIC RULE
We need strategies for activity selection at decision points. Each priority
rule has a characteristics and predictable behavior. Obviously when the
priority rules are combined together, the behavior would be changed and
new behavior depends on what kind of combination has been made. It can
be applied with simple or combined form. In simple form priority rules
may be used in the single form, situational or fixed without any composition
or condition. Also priority rules can be applied sequential that means
some priority rules used as sequential at several steps. It can be situational
or fixed form. For composition of rules, we can employ two kinds of operators.
They are summation operator and multiplication operator. When two kinds
of priority rules are combined, each priority rule can be used in normal
or reverse form.
There are many priority rules which allow us to schedule project activities,
but not so many when the allocation of resources with limited availability
is concerned, which is the most frequent situation in practice. The main
purpose of this study is to use synergy of rules combination. In this
study, according to the literature we select two priority rules and composite
them. We have kinds of composite rules that their efficiencies must be
evaluated to select the best possible solution.
As mentioned previously, the priority rules can be classified in two
major groups, according to different criteria employed for the type of
information required to calculate a value. The first group is network/resource
based rules which make benefit the information contained in the network
and information about the resource. The second group is the rules dealing
with the type of information required for the networks. According to the
literature (Soroush, 1994). Time Criticality Index is appropriate index
in first group for composition. This priority rule is denoted by T_{CI}
and calculated by criticality percent of each activity in all of simulation
runs.
We applied the number of criticality status for each activity in simulation
runs and calculated the percentage of criticality. Indeed we generated
randomly the activities duration times and simulated the network M times
and computed T_{CI}.
For the parameter indicative of network/resource we have proposed resource
criticality index from the second group, which measures the degree
of criticality of the activity for resource allocation. It is one of the
most important indices for resource analysis and control denoted by R_{CI}.
The activities are being arranged based on the R_{CI} calculated
by dividing activity resource requirement and total resource availabilities.
The new constructive heuristic rule is constructed with the composition
of the T_{CI} and R_{CI} rules that we will call Time
and Resource Criticality Index denoted by (T and R)_{CI}. The
performance of the new rule is investigated by designing experiments and
evaluating each composition scheme.
EXPERIMENTAL DESIGN
It is of interest to evaluate the capabilities and efficiency of (T and
R)_{CI} in the key area of the resource allocation in single project
scheduling. The (T and R)_{CI} has been analyzed with respect
to the solutions obtained with the best heuristic method in literature.
The experience gained in resourceconstrained allocation from heuristic
and optimization procedures has clearly shown that the effectiveness of
both types of procedures is strongly dependent upon the characteristics
of the particular problem being solved.
It has been attempted to have different configurations for network structure
considered in evaluating the alternatives. Having attention to Kurtulus
and Davis (1982), four different types of structures have been considered
for networks of this study. Figure 1 illustrates these
structures. In type A the number of parallel activities is more in the
initial portion of network and less in the final portion (Fig.
1a) while in type B it is less in the initial portion of network and
more in the final portion (Fig. 1b). For type C the
number of parallel and independent paths is high in the network (Fig.
1c) and in type D the number of parallel activities in the initial
or final portion of network does not make so much difference. The paths
are not independent of each other and have common activities (Fig.
1d).

Fig. 1: 
Four types of network structure 
Regarding the duration of activities, we consider a stochastic and continuous
time and each activity has at least the same duration and the same renewable
resource requirements in different network types. A designed experiment
was used to determine the effect of final three forms of how to apply
priority rules in network types. In all cases, four replicates of each
treatment combination were made. Therefore (4 different types of A, B,
C and D)x [(3 single form)+(6 summation operator)+(6 multiplication operator)]
= 60 problems were constructed and solved. The activities durations of
the test networks have been randomly generated with uniform distribution
function. To solve all 60 problems, they were coded in visual basic 6.0.
We have evaluated the different kinds of (T and R)_{CI} efficiency
for the two specific cases. In the first case, its efficiency is measured
against the Best Possible Solution (BPS) that is the minimum of
for each network type. In this case we select the best possible solution
and compare with the other solutions especially with the Minimum Slack
Time solution. As mentioned earlier, in this study we have stochastic
networks with activity continuous time. Therefore the generalization of
Minimum Slack is required. However the total floating time of activities
in PERT type networks is random variable. We applied the generalized Minimum
Slack rule. The average total floating time of activities is being estimated
by simulation. In each run of simulation the activities are being arranged
based on the average total floating time. This rule is denoted by Min
and computed by the following relation:
Based on the above relation the network makespan has been computed by
simulation. We computed the mean of makespan for all of problems through
applying each rule in each type of networks denoted by .
According to the literature (Moder et al., 1983) Min
is applied to a feasible solution better than others. Therefore, by resolving
the resource conflicts with the Min
in comparison to the best possible solution the validation of present
index is approved, which is expressed in percentage denoted by Index of
Best Possible Solution (IBPS) and calculated by the percentage of differences
between
and the best possible solution.
Also the efficiency of the single project environment in larger projects
can be measured with regard to critical path (Maroto et al., 1998).
Hence, in the second case, efficiency of new constructive heuristic rule
((T and R)_{CI}) is measured against mean of Initial Critical
Path which is the mean of M times simulation; the same as makespan ().
Therefore it is expressed in percentage of differences between
and Initial Critical Path and denoted by Index of Critical Path (ICP).
Additionally in this case we compare the initial critical path solution
with other solutions especially with the Min
solution. Thus, by resolving the resource conflicts with the Min
in comparison to other solutions the validation of present selected index
is approved. The two mentioned cases allow us to correctly evaluate efficiency
of (T and R)_{CI}.
RESULTS AND DISCUSSION
The (T and R)_{CI} has been analyzed with respect to the solutions
obtained from one of the best heuristic method in literature. As mentioned,
four different types of A, B, C and D have been considered for experiments.
Table 1 contains the first results which illustrates
the mean of makespan ()
values to compare efficiency of (T and R)_{CI} forms for all selected
networks. In the following we will explain the results and analyze (T
and R)_{CI} efficiency by behavior networks analysis and behavior
indices analysis in details.
Although according to the literature, the Min
is wellknown and one of the best priority rules, in single form its efficiency
is not higher than composed rules. As Table 1 demonstrates,
it has the rank of tenth for network type A, eighth for network type B,
first for network type C and fifth for network type D. Only in one of
four network types (type C) it gained the first rank.
Figure 2 illustrates and compares the efficiency of
Min
against the other considered rules in four networks types. This figure
shows in type A, 53.33% solutions are better than Min ,
while we have 46.66 and 26.66% for types B and D and in type C we have
0%. These percents refer to high efficiency of Min
in type C and low efficiency in type A.
Table 1: 
Illustrates the mean of makespan ()
values in four networks types 


Fig. 2: 
Difference among Min
and other indices in four networks types 
Table 2: 
The comparison of results of IBPS and ICP in four networks
types 

Also Fig. 2 indicates in single form of (T and R)_{CI}, we find the best possible
solution only in type B network. It means in most of the networks types,
combined forms provide better results than simple forms. All of these
results illustrate the synergy of rules composition. Indeed results confirm
that combinations of heuristics can be used to find better solutions to
resource allocation problems than single heuristics.
As the results indicate, for type A, 13.33% indices have been found the
best possible solution with project makespan 39.85, while for type B we
have 33.33% with project makespan 42.89. Also for type C we have the best
possible solution 13.33% with project makespan 46.08 and in type D we
have 6.66% with project makespan 40.09.
Regarding the interaction (T and R)_{CI} by four networks, as
mentioned, the analysis is performed for two cases for comparison of the
schedules when the project resources have limited availabilities. The
first case is formed by the best possible solution which presents a high
performance and the second case is formed by critical path.
Table 2 gives the percent differences among the (T
and R)_{CI} values ()
with the best possible solution (minimum of )
and Initial Critical Path (ICP). The interpretation is that comparing
the (T and R)_{CI} with the best possible solution (IBPS) indicates
that say for network type A, 12.65% difference between the best possible
solution and worst solution is observed. Also for network type B, 6.99%
difference is observed. For network type C and network type D, the 13.02
and 16.86% differences are observed, respectively.
As Table 2 indicates, comparing the (T and R)_{CI}
with Index of Critical Path (ICP), in type A, we have 32.79% differences
between the best possible solution and initial critical path and 49.58%
differences between the worst solution and initial critical path. It says
that we have range values around 16.79% difference.

Fig. 3: 
Comparing of Max (T* R) results with other major indices
Max (T), Max (R) and Min SLACK 
Also in type B we
have a range percent difference between the best possible solution (77.52%)
and worst solution (89.94%) about 12.42% difference. For type C we have
the range between 60.11 and 80.96% that indicates around 20.85% difference.
At least we have 21.88% difference between the best possible solution
(29.74%) and the worst solution (51.62%) in type D. With respect to the
above results it appears that the differences between the network types
of A and B are similar; while results of network type C is similar to
network type D. Regarding the best possible solution (IBPS) and Index
of Critical Path (ICP) percents, it can be said that the network structure
plays an important role in efficiency of (T and R)_{CI}.
Table 2 shows the performance of Max (T* R). The results
of Max (T* R) are also surprising. This index is the best possible solution
for different network types of A, B and C. Also for network type D, Max
(T + R) index is the best possible solution with IBPS=0.00% and ICP=29.74%.
If we compare these results with Max (T* R) for type D (IBPS= 0.07 and
ICP=29.84%), it appears that the differences between the results are very
low. Therefore we can use Max (T* R) index instead of Max (T* R) index.
Indeed we can consider Max (T* R) index as common and distinct solution
for all of four networks types.
Fig. 3 clearly displays comparison results of Max (T*
R) with two major indices Max (T), Max (R) and wellknown heuristics Min
in four networks types. Max (T* R) presents the most efficient solution
with reference to resource constrained project scheduling. However because
of problem complexity, its quality of solutions compared with the optimal
solutions is unknown.
CONCLUSION
The main objective of this study was to develop a new constructive heuristic
rule as a computationally simple method to find good solutions to ResourceConstrained
Project Scheduling Problem (RCPSP). The new composed rule, developed for
stochastic problems, was adapted to the resource allocation problem with
activity continuous distribution function and demonstrated on an established
test set of resource allocation problems. The new composed rule performed
well compared to other wellknown heuristics like Min ,
that according to the literature it is one of the best wellknown priority
rules. In investigation of 60 problems, the experiments show that, Max
(T* R) was able to find the best possible solution for all of four types
of networks.
Present evaluation has demonstrated that the area in which there are higher
differences regarding capabilities and efficiency of the indices for resourceconstrained
project scheduling, we could construct a new constructive rule (Max (T* R))
with composition of T_{CI} and R_{CI}, that its efficiency is
superior to both rules. The experiments confirmed the synergy of rules composition
and illustrated that composition of heuristics can be used to find better solutions
to resource allocation problems than single heuristics. Some indices only allow
the consideration of simple networks, while others also include complex networks.
Finally, regarding the criteria for resource allocation to different activities
in the resolution of the mentioned problems, Max (T* R) is more appropriate
than other indices in this sense.
To correctly evaluate the efficiency of the schedules provided with the
different indices, we have created two designs of experiments, one in
the scheduling of constrained resources in single projects with the best
possible solution and the other with Index of Critical Path (ICP). In
both we have generated instances in which all the relevant project characteristics
have been experimented. The results point out the significant differences
in performance of the different indices. Thus, Max (T* R) was the most
efficient because it offers the schedules with the shortest duration,
even better than the other indices, such as single form, multiplication
form and summation form. It is also remarkably to note that the most efficient
indices have a better performance than the classical methods such as Min
.