Subscribe Now Subscribe Today
Research Article
 

Development of a Constructive Heuristics Rule for Constrained Resource Allocation in Stochastic Networks



M. Rabbani, S. Baradaran, S.M.T. Fatemi Ghomi and S.S. Hashemin
 
ABSTRACT

This study presents a constructive heuristic for constrained resource allocation in PERT type networks. The problem consists in scheduling a project, i.e., a set of activities (or tasks) linked by precedence constraints should be scheduled subject to resource constraints while minimizing the total duration of the project (the so called makespan). The assumption is made that the constrained resource is renewable for allocation to the activities of project. The activities durations are independent continuous random variables, preemption is not allowed and renewable resource requirements are constant throughout the duration of an activity. Project scheduling problems of this type belong to the class of NP-hard optimization problems. So, to solve this type of problems, heuristic procedures should be used. We developed a new constructive heuristic rule ((T and R)CI) and evaluated through design of experiments. The experiments show the efficiency of new rule and it performed well, compared to well-known criterion of minimum slack time.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

M. Rabbani, S. Baradaran, S.M.T. Fatemi Ghomi and S.S. Hashemin, 2008. Development of a Constructive Heuristics Rule for Constrained Resource Allocation in Stochastic Networks. Journal of Applied Sciences, 8: 3917-3923.

DOI: 10.3923/jas.2008.3917.3923

URL: https://scialert.net/abstract/?doi=jas.2008.3917.3923

INTRODUCTION

The general Resource-Constrained 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 (Alvarez-Valdes 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 NP-hard 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 heuristic-based 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 well-known, 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 well-known priority rules, Time Criticality Index (TCI) and Resource Criticality Index (RCI). 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 Resource-Constrained Project Scheduling Problem (RCPSP) can be stated as follows:

Project network G (N, A) is shown as PERT type network with an Activity-On-Arc (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 finish-start relations with a minimal time-lag 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:

(1)

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 TCI 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 TCI.

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 RCI. The activities are being arranged based on the RCI calculated by dividing activity resource requirement and total resource availabilities.

The new constructive heuristic rule is constructed with the composition of the TCI and RCI 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 resource-constrained 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:

(2)

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 well-known 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 well-known 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 Resource-Constrained 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 well-known heuristics like Min , that according to the literature it is one of the best well-known 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 resource-constrained project scheduling, we could construct a new constructive rule (Max (T* R)) with composition of TCI and RCI, 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 .

REFERENCES
Alvarez-Valdes, R., E. Crespo, J.M. Tamarit and F. Villa, 2006. A scatter search algorithm for project scheduling under partially renewable resources. J. Heuristics, 12: 95-113.
CrossRef  |  

Blazewicz, J., J.K. Lenstra and A.H.G.R. Kan, 1983. Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Math., 5: 11-24.
CrossRef  |  Direct Link  |  

Bouleimen, K. and H. Lecocq, 2003. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. Eur. J. Operat. Res., 149: 268-281.
CrossRef  |  

Brucker, P., A. Drexl, R. Mohring, K. Neumann and E. Pesch, 1999. Resource-constrained project scheduling: Notation, classification, models and methods. Eur. J. Oper. Res., 112: 3-41.
CrossRef  |  Direct Link  |  

Demeulemeester, E. and W. Herroelen, 2002. Project Scheduling: A Research Handbook. Kluwer Academic Publisher, Boston, MA., USA., ISBN-13: 9781402070518, Pages: 685.

Herroelen, W. and R. Leus, 2005. Project scheduling under uncertainty: Survey and research potentials. Eur. J. Operat. Res., 165: 289-306.
CrossRef  |  Direct Link  |  

Herroelen, W., E. Demeulemeester and B. De Reyck, 1998. A Classification Scheme For Project Scheduling. In: Handbook on Project Scheduling: Recent Models, Weglarz, J. (Ed.). 1st Edn., Algorithms and Applications, Kluwer, Boston, ISBN: 0-7923-8268-4, pp: 1-26.

Kolisch, R. and R. Padman, 2001. An integrated survey of deterministic project scheduling. Omega, 29: 249-272.
CrossRef  |  

Kolisch, R. and S. Hartmann, 1998. Heuristics Algorithms for the Resource Constrained Project Scheduling Problem: Classification and Computational Analysis. In: Handbook on Project Scheduling: Recent Models, Weglarz, J. (Ed.). 1st Edn. Algorithms and Applications, Kluwer, Boston, ISBN: 0-7923-8268-4, pp: 147-178.

Kolisch, R. and S. Hartmann, 2006. Experimental investigation of heuristics for resource-constrained project scheduling: An update. Eur. J. Opera. Res., 174: 23-37.
CrossRef  |  

Kurtulus, I. and W. Davis, 1982. Multi-project scheduling: Categorization of heuristic rules performance. Manage. Sci., 28: 161-172.

Liess, O. and P. Michelon, 2008. A constraint programming approach for the resource-constrained project scheduling problem. Ann. Operat. Res., 157: 25-36.
CrossRef  |  

Maroto, C., P. Tormos and A. Lova, 1998. The Evolution of Software Quality in Project Scheduling. In: Handbook on Project Scheduling: Recent Models, Weglarz, J. (Ed.). 1st Edn. Algorithms and Applications, Kluwer, Boston, ISBN: 0-7923-8268-4, pp: 239-258.

Mika, M., G. Waligóra and J. Weglarz, 2005. Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models. Eur. J. Operat. Res., 164: 639-668.
CrossRef  |  

Moder, J.J., C.R. Phillips and E.W. Davis, 1983. Project Management with CPM, PERT and Precedence Diagramming. 2nd Edn., Van Nostrand Reinhold International Company Limited, New York, ISBN: 0-442-25415-6.

Soroush, H.M., 1994. The most critical path in a PERT network: A heuristic approach. Eur. J. Operat. Res., 78: 93-105.
CrossRef  |  

Sprecher, A., R. Kolisch and A. Drexl, 1995. Semi-active, active and non-delay schedules for the resource-constrained project scheduling problem. Eur. J. Operat. Res., 80: 94-102.
CrossRef  |  

©  2019 Science Alert. All Rights Reserved