1. INTRODUCTION AND BACKGROUND
The resource constrained project scheduling problem (RCPSP) is a strongly NPhard. In other words, there is no any algorithm to obtain the optimal solution of RCPSP in polynomial time Lensra and Rinnooy Kan (1978). Exact methods and heuristic methods are two main groups to classify scheduling schemes. For the first one, we can refer to for instance: mathematical modeling (Icmeli and Rom, 2015), dynamic programming (Petrovic, 1968) and branch and bound. The main drawback of exact methods is that they can only applicable to solve the scheduling problem up to 120 activities (Browning and Yassine, 2009; Yoosefzadeh et al., 2010). Some (meta)heuristic methods for solving the RCPSP are listed as: single and multipass, and sampling methods, genetic algorithms, simulated annealing (e.g. Bouleimen and Lecocq, 2003; Hartmann, 2002), tabu search and the artificial immune system (e.g. Agarwal et al., 2007).
The serial scheduling scheme (SSS) and the parallel scheduling scheme (PSS) are two schedule generation schemes (SGS) which is proposed by Herroelen (2005) that both generate feasible schedules. The heuristics that are capable to deal with real world large instances of the RCPSP do not guarantee to yield the optimal solution. Hence, it is nearly always possible to improve the performance of these heuristics. During the last decades many improvements to such heuristics have been proposed.
For the first time in 2000, the bidirectional scheduling scheme (bidss) was proposed by Klein in (Klein and Scholl, 2000). The numerical results showed that bidss outperforms the single directional scheduling schemes such as forward and backward schemes even by using SSS or PSS (Klein, 2000). Tridirectional scheduling scheme (trdss) which is introduced in (Kanit et al., 2009) produces schedules with high quality (shorter makespans). It is worth noting that the quality of feasible solution which is obtained by trdss is depending on two factors: problem structure and priority rules. Note that Davis and Patterson reported three important characteristics in the structure of the RCPSP: an activity’s resource utilization {RF, RS} the ratio of average slack per activity to the critical path length and project complexity (the notation C as used in Kumanan et al., 2006).
The effective of heuristics/metaheuristics performance is due to which priority rules uses (See e.g. Shukla et al., 2008). Because of speed and simplicity of priority rules, they are formed the base of commercial project scheduling software packages. Networkbased rules, critical pathbased rules and resourcebased rules are three main groups for categorizing the priority rules (Shukla et al., 2008). Some project’s characteristics such as type and number of resources, number of activities’ mode, number precedence constraints, objectives function and etc. can be affected on performance of priority rules. In other words, there is no any specific priority rule that generate the best schedule in all of projects. In (Yoosefzadeh et al., 2013) numerical results showed that among all of priority rules the ones which are uses the time and resource as their input values usually outperform others. In (Yoosefzadeh and Tareghian, 2013) the correlation between the number of resource constraints and the kind of priority rules are investigated. Ulusoy and Ozdamar reported that the percentage of critical activities, network complexity, resource measures, obstruction value and utilization factor are important in deciding upon successful priority rules.
In this paper, the RCPSP that is considered is as follow (the RCPSP with notation PSmcpmCmax): The project with N activities (activities 1 and N are dummy activities and show the start and the end of the project respectively) which is considered as an activity on node network (AON). Each activity j has a constant processing time (duration) of d_{j}. No preemption during the processing time of activities is defined. The precedence relations between activities are defined by finish to start control. Activity j needs $\hspace{0.17em}\hspace{0.17em}{u}_{jr}(j=2,\hspace{0.17em}\hspace{0.17em}\dots ,N1;\hspace{0.17em}\hspace{0.17em}r=1,\hspace{0.17em}\hspace{0.17em}\dots ,\hspace{0.17em}R)$ units of resources in each period of its duration. The availability of renewable resources ${a}_{r}\hspace{0.17em}\left(r=1,\hspace{0.17em}\hspace{0.17em}\dots ,\hspace{0.17em}\hspace{0.17em}\leftR\right\right)$ in each period of time is constant. A schedule S is said to be feasible if both the precedence and the resource constraints are satisfied. Minimizing the makespan of the project is defined as our objective function.
In this paper, in the light of some resource characteristics (knowing as resource complexity measures) of the RCPSP that affect the quality of the solution, we try to answer the following question:” when is it beneficial (obtain a solution with smaller makespan) to move to higher directional scheduling schemes?.” The rest of the paper is organized as follows: In Section 2 we briefly describe multidirectional scheduling schemes such as the bidss and the trdss. In Section 3, the results of the experiments according to the some resource complexity measure are reported and discussed in details. The conditions under which moving to higher directional scheduling schemes leads to better solutions are also cited. Finally a summary and conclusions are given in Section 4.
2. MULTIDIRECTIONAL SCHEDULING SCHEMES
In this section, in order to answer the mentioned question i.e. “when is it beneficial to move to higher directional scheduling schemes,” two multidirectional scheduling schemes, are briefly explained. We also present the outline of the bidss and the trdss. It is worth noting that in this paper the PSS of Brooks form the base of multidirectional scheduling schemes. In our study the priority rules that are listed.
2.1. Bidirectional Scheduling Scheme
In 2000 Klein proposed the bidss and according to the numerical results showed that in the light the PSS or SSS, the performance of the bidss is better than the forward or backward scheduling schemes.
Initialization phase and interlinking phase are two main phases of the bidss. In the initialization phase, the activities are scheduled in two separate directions. At any scheduling time, t, activities that have all their predecessors completed are scheduled in their left most positions of their time windows where no violations of resource constraints occur (forward direction). On the other hand, activities that have all their successors planned are scheduled in their right most positions of their time windows where no violations of resource constraints occur (backward direction). Activities that are eligible for scheduling at either direction are scheduled according to a tiebreaking rule. As such, some of them are forward scheduled, whilst others are backward scheduled. In the interlinking phase the backward scheduled activities are left shifted to interlink the forward and backward scheduled activities and obtain the complete schedule. The backward scheduled activities are left shifted according to some specific order (See Yoosefzadeh and Tareghian, 2013 for more detail). The outline of the bidss is given in Figure 1. The notations used are as follows:

R : Set of available resources

C_{n} : Set of completed activities at stage n

D_{n} : Set of eligible activities at stage n

πa_{r} : Remaining capacity of resource r at any stage

P_{i} : Set of predecessors of activity i

υ(i) : Priority value of activity i

t_{n} : Scheduling time at stage n

J : Set of project activities

A_{n} : Set of ongoing activities at stage n
Note that indices f and b refer to forward and backward directions, respectively. Furthermore, the set ES(t = k) contains all the eligible activities at time t = k.
2.2. TriDirectional Scheduling Scheme
The trdss is the same as the bidss except for the trdss some activities are forward scheduled, some others are backward scheduled but the activities that are eligible to be scheduled in either forward or backward directions are now scheduled in midway direction. In order to facilitate the understanding of the conceptual differences between the two schemes, we present in Figure 2, the outline of the trdss exactly as presented in (Yoosefzadeh and Tareghian, 2013). The given notations are the same as in Figure 1. However, index m refers to the midway direction.
3. ANALYSIS OF RESULTS
In this section we describe the experiments and discuss the results. All the experiments were programmed by MATLAB R2014a and executed on a PC Pentium 4 with CPU 4.2 Intel. We have based our investigations on two different sets of benchmark instances. One is due to Kolisch’s benchmark and the other is due to AlvarezValdez & Tamarit. Regarding our investigations, both instances produce similar results. For the sake of brevity, the results obtained by the 1st benchmark problems are only presented. However, in appendix, some results obtained using the 2nd benchmark instances are also presented and briefly discussed.
3.1. Quality of Solutions
We initially examine the performance of the sidss, the bidss and the trdss on more extensive benchmark problems. We use the sidss, namely forward scheduling, the bidss and the trdss to solve the J90 and the J120 sets of the first benchmark problems. As in (Yoosefzadeh and Tareghian, 2013), the number of instances solved to optimality, the number of best instances, and the average relative deviation from the optimal solution and the best solution obtained are the comparison measures. The related results are given in Tables 14.
The columns 5 and 9 of these tables display the percentage improvement of the trdss in comparison to the bidss. To explain more, take a look at Table 1, for example. With LST as the priority rule (Latest Starting Time), the trdss solves 3.68% more instances to optimality than the bidss. This improvement is 2.2% under MIS as the priority rule. The number of best instances shows similar trend. Under GRPW, the number of best solutions obtained by the trdss is 34.3% more than the bidss. Note that when WRUP is used as the priority rule, this improves to 45.9%. Table 3 for J90 shows similar results.
Tables 2 and 4 depict the average deviations from the optimal solutions and the best solutions for J120 and J90, respectively. In Table 2, the range of average deviation from the optimal solutions is $\hspace{0.17em}\left[0.12\%\hspace{0.17em}\hspace{0.17em},\hspace{0.17em}\hspace{0.17em}13.37\%\right]$ in favor of the trdss. The results displayed in column 5 of Table 2 show that the solutions obtained by the trdss have always lower average deviation from the optimal solutions irrespective of the priority rule used. Comparing the results of Tables 2 and 4, it seems that as the size of the project (number of activities) is increased, the quality of the solutions as measured by their average deviations from the optimal solutions is also increased.
On the basis of the results presented in Tables 14, is it possible to deduce that for solving an instance of the RCPSP, moving from the sidss to the bidss and to the trdss always lead to better solutions? If not, is it then possible to determine the most influential factors that affect the performance of these schemes? As the results indicate the rate of the improvements in the solutions yielded by the bidss and also by the trdss is variable when compared to the sidss. Could this be due to the different influence that the factors have on the performance of the bidss and the trdss?
To find the answers to the given questions we performed a comprehensive study which we explain in the following sections.
3.2. Solutions Behavior
In order to evaluating of influential factors that affect the performance of sidss, bidss and trdss, we categorized the benchmark problems into two groups based on their solutions behavior. First we give the following definitions
Definition 1: Let ${T}_{w}(j)$ be the makespan of the problem j obtained by the scheduling scheme $\hspace{0.17em}\hspace{0.17em}w\in \left\{\hspace{0.17em}sidss,\hspace{0.17em}\hspace{0.17em}bidss,\hspace{0.17em}trdss\hspace{0.17em}\right\}$. Let $SR=PR\cup NR$ be the set of problems that when solved by w produces a regular pattern, i.e.:
and
Definition 2: Let IR be the set of problems that when solved by w produces an irregular pattern, i.e. $\hspace{0.17em}IR=\left\{\hspace{0.17em}j\hspace{0.17em}j\notin SR\hspace{0.17em}\right\}$.
Based on definitions 1 and 2, Table 5 displays the number as well as the percentage of the instances of the J90 and J120 benchmark problems that belong to set SR and the subset PR. The number of J90 and J120 problems that we used in our experiments is 480 and 434 problems, respectively. To illustrate Table 5, consider LPT as the priority rule, then column 3 of the Table states that 95% of the benchmark problems (412 out of 434) belong to the SR from which 91% (i.e. 376 out of 412) belong to the PR. A closer look at Table 5 reveals that in J120 benchmark problems, between 5695% of the problems instances belong to the SR from which between 7797% of instances fall in the PR. The same trend can be seen for J90 benchmark problems (at least 83% of the instances of J90 fall in the SR, 91% of which fall in the PR). Averaging columns 3 and 7 of Table 5, we realize that 82.7% of all the instances (i.e. J90 ∪J120) fall in the SR of which 92.2% belong to PR.
Therefore, it can be seen that increasing the direction of the scheduling scheme has a positive effect of the quality of the solutions obtained.
Could the better performance of the trdss be only attributed to the number of activities that are being shifted in the trdss? Could not the actual separation of activities onto forward, midway and backward have a meaningful effect on the trdss performance?
Table 6 displays the results of our studies about these questions. Columns 2 and 4 of Table 6 show the % of the problems in PR that satisfy the following condition with respect to the J120 and the J90 instances respectively:
With reference to Table 6 and considering SPT as the priority rule, it is evident that 94.4% (334 out of 354) of the problems in PR satisfy (1). However, for J90 instances, 95% (415 out of 437) of the problems in PR satisfy the above condition. Results show that in more than 93% of the problems in PR (J90 ∪J120), the solution by the trdss has lead to more activities being shifted when compared to the bidss. Therefore, the first factor which is influenced the schedules makespan positively is the number of shifted activities.
Columns 3 and 5 in Table 6 display the number (and the %) of the problems for which the trdss has performed better than the bidss in spite of the fact that the following condition holds:
For example in column 5 and under GPRW, the trdss outperforms the bidss in 100% of J90 instances that satisfy (2). Averaging percentages in columns 3 and 5, we realize that in nearly 83.5% of all instances that satisfy (2), the trdss outperforms the bidss. In other words, the separation of activities affects the quality of the schedule thus obtained positively. Therefore, the better performance of the trdss, at least on these instances, can be attributed to the separation of the activities.
With reference to Table 6, it is evident that not only the number of the activities that are being left shifted in the interlinking phase affects the quality of the solutions, but the separation of the activities into different groups also plays an important role.
3.3. Influence of the Resource Parameters
A number of studies have shown that the density of the coefficient matrix reflected by resource factor (RF), the availability of resources measured by resource strength (RS) and also the longitudinal distribution or loading of resource requirements across the problem duration measured by average resource loading factor (ARLF) are among the most important parameters that control the difficulty of an instance of the RCPSP and hence affects the quality of the solution. Therefore in this paper we just evaluate the effect of these resource factors on comparing the quality of the solutions with respect to applying scheduling schemes.
3.3.1. Resource Factor
Resource factor (0 ≤ RF ≤ 1) is a measure of the average number of resources used by an activity. As RF tends to 1, reflecting higher dependence on resources, the problems becomes more complex. Table 7 reflects the effect of RF levels on cardinality of SR and IR sets. For example, for level RF = 0.75, average number of instances which are belongs to SR and IR sets, are 105.2 and 8.4, respectively. Figure 3 displays the average number of problems (averaged over all used priority rules) in PR and NR versus resource factor. The curves with solid and dashed lines correspond PR and NR, respectively. For example, on average 8.58 problems that belong to the NR and nearly 99.7 problems that belong to PR have RF = 0.25 (i.e. PR is 1062% more than NR ). For RF = 1.00, on average 81.8 problems belong to the PR and nearly 4.8 problems belong to the NR. Therefore, by considering the results it seems that as the amount of RF decreases, move to higher directional scheduling schemes becomes more beneficial. It is noteworthy that if the dependency on number of used resources by any activity decreases then the flexibility of activities for scheduling grows up (because constraints on any activity decrease). Hence more flexible activities for scheduling, device more increase in number direction.
3.3.2. Resource Strength
Resource strength (0 ≤ RS ≤ 1) describes the relationship between resource requirements and resource availability. As RS tends to 1, it implies that there are in general more available resources than required, therefore the complexity of the problem decreases. In fact the problems with RS =1.0 are no longer resourceconstrained.
Based on Table 8, it is observed that as the level of RS decreases, the cardinality of IR set increases.
It is worth noting that, for the project with RS =1.0 , each of three scheduling schemes i.e. the sidss, bidss, and trdss will produces the optimal solution that is equal to the corresponding length of critical path, because each activity is scheduled in the earliest starting time. So these instances are excluded from the more examining.
Figure 4 displays the average number of problems (averaged over all used priority rules) in PR and NR versus resource strength. For example, on average 74.8 problems that belong to the PR and nearly 12 problems that belong to NR have RS = 0.2 and for RS =1.0 , on average 3.7 problems belong to the NR and nearly 92.2 problems belong to the PR.
Note that as RS tends to 1, use of higher directional scheduling schemes tends to reduce the makespan (similar to the case where RF tends to zero).
Remark As the flexibility of activities in scheduling is increased (i.e. RF → 0.0 or RS → 1.0 ), the cardinality of PR increased, therefore one can deduced that the increasing of scheduling dimension from 1 to more, becomes more beneficial, i.e. leads to increasing in makespan’s improvement.
3.3.3. Average Resource Loading Factor
In 1982, Kurtulus, et. al. proposed average resource loading factor ($ARLF\in \mathbb{R}$) as another measure of resource usage distribution. ARLF identifies whether the bulk of a project's total resource requirements are in the front or back half of its critical path duration and the relative size of the disparity. ARLF is defined as follows:
where ${X}_{it}=\left\{\begin{array}{l}\hspace{0.17em}1\text{\hspace{1em}}\hspace{0.17em}if\hspace{0.17em}activity\hspace{0.17em}\hspace{0.17em}i\hspace{0.17em}\hspace{0.17em}is\hspace{0.17em}active\hspace{0.17em}at\hspace{0.17em}time\hspace{0.17em}\hspace{0.17em}t\\ \hspace{0.17em}0\text{\hspace{1em}}otherwise\end{array}\right\},\hspace{0.17em}{Z}_{it}=\left\{\begin{array}{l}1\text{\hspace{1em}}t\le \raisebox{1ex}{$L$}\!\left/ \!\raisebox{1ex}{$2$}\right.\hspace{0.17em}\hspace{0.17em}\\ +\hspace{0.17em}1\text{\hspace{1em}}t>\raisebox{1ex}{$L$}\!\left/ \!\raisebox{1ex}{$2$}\right.\end{array}\right\},$
N is the number of total activities of the project(the size of the project), u_{ik} is the amount of resource type k required by activity i, K_{i} is the number of different resources required by activity i and finally, L is the length of the critical path of the project (based on scheduling each activity at its earliest starting time). Projects with ARLF < 0 are frontloaded in their resource requirements and projects with ARLF > 0 are backloaded. For the project with ARLF ≈ 0, the resource distributions in left and right side of $t=\raisebox{1ex}{$L$}\!\left/ \!\raisebox{1ex}{$2$}\right.$ are approximately the same (Yoosefzadeh and Tareghian, 2013).
For the purpose of our study, we slightly modified (1) as follows:
where $\hspace{0.17em}lef{t}_{it}=\left\{\begin{array}{l}+1\text{\hspace{1em}}\hspace{0.17em}\hspace{0.17em}t\le \raisebox{1ex}{$L$}\!\left/ \!\raisebox{1ex}{$2$}\right.\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\\ \hspace{0.17em}\hspace{0.17em}0\text{\hspace{1em}}\hspace{0.17em}\hspace{0.17em}t>\raisebox{1ex}{$L$}\!\left/ \!\raisebox{1ex}{$2$}\right.\end{array}\right\}$. The other notations are exactly as used in (1). The modified factor indicates the amount of resource distributions in the left side of $\hspace{0.17em}t=\raisebox{1ex}{$L$}\!\left/ \!\raisebox{1ex}{$2$}\right.$. Note that in a project with the specified size, as the number of activities in the left side of $\hspace{0.17em}t=\raisebox{1ex}{$L$}\!\left/ \!\raisebox{1ex}{$2$}\right.$ increases, then the amount of ARLF_{left} increases (It is indicated by notation ARLF_{left} ↑ ).
Using (2) and with respect to the following three intervals: [ 43, 67.4], [67.4,73.5] and [ 73.5,90], we grouped the available benchmark instances (J120 ∪J90) into three different sets with nearly equal cardinality. So by considering $\left\hspace{0.17em}SR\hspace{0.17em}\right,\hspace{0.17em}\hspace{0.17em}\left\hspace{0.17em}IR\hspace{0.17em}\right$ and the new measure as defined in (2), we found that as the resource distributions in the left side of $t=\raisebox{1ex}{$L$}\!\left/ \!\raisebox{1ex}{$2$}\right.$ increase ( ARLF_{left} ↑ ), on average, SR increases, but IR decreases (see Figure 5).
For example, in the first interval we have on average $\left\hspace{0.17em}SR\hspace{0.17em}\right=122.15$ and $\hspace{0.17em}\left\hspace{0.17em}IR\hspace{0.17em}\right=30.35$. However, in the last interval, we have on average $\left\hspace{0.17em}SR\hspace{0.17em}\right=131.04$ and $\hspace{0.17em}\left\hspace{0.17em}IR\hspace{0.17em}\right=21.96$. Table 9 shows the effect of ARLF_{left} on $\leftPR\right$ and $\leftNR\right$. It is evident that as ARLF_{left} increases (i.e. ARLF_{left} ↑), $\leftNR\right$ (is negligible) decreases and $\leftPR\right$ increases.
More investigations show that, as ARLF_{left} ↑ , the resources contention in the left side of $\hspace{0.17em}t=\raisebox{1ex}{$L$}\!\left/ \!\raisebox{1ex}{$2$}\right.$ increase and subsequently this factor leads to increasing in the number of activities in the mid ∪ right subschedules of the trdss. Hence, as mentioned before, increasing the number of shifted activities yields better quality solutions (smaller makespan), especially in the trdss.
With reference to Table 5, $\leftIR\right$ in comparison to $\leftSR\right$ is insignificant and in some cases is negligible. However, in order to provide clearer picture of the effect of ARLF_{left} , we further partitioned IR = IR_{1} ∪ IR_{2} in two subsets as follows (Definition 1 applies):
Figure 6 shows that on average the number of instances in IR_{1} becomes greater than IR_{2} when ARLF_{left}↑. Note that IR_{1}set is more sensitive than IR_{2}set to the ARLF_{left} variation. In other words, as $ARL{F}_{left}\uparrow ,\hspace{0.17em}\leftI{R}_{1}\right$ takes the increasing values corresponding to the three intervals. However, $\leftI{R}_{2}\right$ remains nearly unchanged.
Based on the results of our experiments, we came to the conclusion that besides the factors such as RF and RS, ARLF_{left} can also be used as an indicator for moving to higher directional scheduling schemes. Our results show that as ARLF_{left}↑, on average the trdss performs better than the bidss and therefore it is beneficial to use trdss instead of bidss.
Observation 1: As ARLF_{left} ↑, it seems that the xdirectional scheduling scheme (xdss) cause to smaller makespan than ydss if x > y ≥ 1 .
Lemma: Suppose that in the interlinking phase of an xdirectional scheduling scheme (xdss) where x ≥ 2 , as x increases, more activities are being shifted. Let increasing the number of shifted activities leads to more improvements to the project’s makespan. Then the percentage of improved makespans using xdss is more than the percentage of improved makespans using ydss (x > y) as the size of the project (number of activities) increases.
Proof. (Yoosefzadeh and Tareghian, 2013).
Observation 2: It seems that any factor that lets more activities to be left shifted, prepares the ground for improving the makespan. This is more evident in the trdss than the bidss.
Using the lemma, it can be claimed that on average the xdss provides better solutions in quality (smaller the makespan) than ydss (x > y ≥ 2).
4. CONCLUSIONS
In this paper, we addressed the question: when is it beneficial (obtain a solution with smaller makespan) to move to higher directional scheduling schemes? We first showed that not only the number of the activities that are being left shifted affects the quality of the solutions, but also the separation of the activities into different groups plays an important role in the makespan reductions (as mentioned in (Yoosefzadeh and Tareghian, 2013). Based on the results of the experiments, we concluded that as RF → 0.0 or RS → 1.0 , moving to higher scheduling direction schemes is beneficial and leads the makespans improvement. We modified the average resource loading factor (ARLF_{left} ) in order to use it as another indicator regarding the use of higher directional scheduling schemes. We found that as the ARLF_{left} increases, the tridirectional scheduling scheme performs better than the bidirectional and the single directional schemes. The author is presently working on the optimum number of x in the xdss.
Appendix
In the following we present a small sample of the results obtained when we applied our proposed scheduling scheme (mtrdss) to the AlvarezValdez & Tamarit’s benchmark instances (2nd benchmark). In this benchmark, the instances are more constrained with respect to resources. However, the results obtained are similar to the results of the kolisch’s benchmarks. For the sake of brevity we only present the results and figures related to the $ARL{F}_{left}$ and briefly discuss them.
We initially grouped the instances with 103 activities into three different sets with equal cardinality as $[\hspace{0.17em}44,\hspace{0.17em}\hspace{0.17em}50.45\hspace{0.17em}]$, $[\hspace{0.17em}50.45,\hspace{0.17em}\hspace{0.17em}53.35]$ and $[\hspace{0.17em}53.35,\hspace{0.17em}70\hspace{0.17em}]$. Figure A1 shows, as $ARL{F}_{left}\uparrow ,$ as before, the cardinality of $PR$ increases but the cardinality of decreases (so similar arguments regarding Figure 6 applies. In Figure A2, we present the effect of $ARL{F}_{left}$ variations on the cardinality of $I{R}_{1}$ and $\hspace{0.17em}\hspace{0.17em}I{R}_{2}$. This Figure also shows similar trend to Figure 7, i.e. $I{R}_{1}$ is more sensitive than $I{R}_{2}$ to the $ARL{F}_{left}$ variations.