1. Introduction

RCPSP (Resource-Constrained Project Scheduling Problem) is scheduling the project activities according to precedence relations and constraint of resources. RCPSP consists of a project with j activities j=1, …, j. the duration of an activity j is donated by All activities can start just once, and they can be preemptive or not. Because of technical needs, there is some precedence relations among activities donated as a set of relations . It shows that activity j cannot be started unless all of its precedence relations and precedents are fulfilled. Precedence relations can be represented by an AON (Activity on Node network); with the presupposition of acyclic feature of the network. Each activity needs a special amount of resources for completion and execution [1].

In standard RCPSP, an activity can only be executed in one way. So the execution time and amount of needed resources will be definite [1].

First research on multi-state activities has been done by Elmaghraby [2]. An activity, which only could have been executed in one way in standard state, now can be executed in several states or methods. Each state needs its own execution time and needed resources.

Multi-state RCPSP is shown MRCPSP in this problem. RCPSP problem has a presupposition of being multi-state. This presupposition is defined as follows:

"An activity j must be started at one point and must be executed in one of its execution states which is shown by 1,…, The activity must be terminated in the same execution state which it had been started. Preemption is not suitable in the basic model of MRCPSP [2]. The execution time for activity j in state m is shown by The amount of resource needed for execution of activity j in state m is shown by . Besides the renewable resources, non-renewable resources are also being used in multi-state models. A scheduling plan for multi-state RCPSP model is specified with a start time and a state for each j activity. The most well-known target function in these kinds of problems is minimizing the project makespan. [2]"

It's obvious that if there is only one state for each activity, and there will be no non-renewable resource, the problem will turn into a standard RCPSP problem. It should be mentioned that including a non-renewable resource there is a chance that we couldn’t have any feasible scheduling, and this has been indicated by Kolish and Drexl [3]. The problem of finding a feasible scheduling in this problem is a kind of NP-Complete problem itself (in case there exist at least two non-renewable resources considered for the problem). According to Broker et al. symbolization, parameter α will be started with MPS [4].

2. Proposed Bi-objective MRCPSP Problem

According to the literature that has been reviewed, the proposed model has been considered in Bi-objective state [5], multi-mode state, with renewable or non-renewable resources and dual resources which is a particular state of resources.

Also for the goals, two well-known and practical goals has used which the first one is minimizing project makespan and the second one is minimizing project total cost.

The mathematical model for the proposed problem is as follows:

Constraint 1 is like a basic MRCPSP problem which causes the activity to be started in any executive mode and specified time that had been chosen and other modes will not be used until the end of the execution.

Constraint 2 is the end-to-start precedence relations constraint. If this constraint is used between activities i and j, activity j won't start unless the activity i finished.

Constraint 3 is the constraint of renewable resources which is the basic model of MRCPSP.

Constraint 4 is the constraint of non-renewable resources which is the basic model of MRCPSP.

Constraint 5 is the constraint of decision variable being binary.

Now we should mention two important notes about project cost function and dual-resource constraint. According to the fact that the cost constraint of each activity is a kind of inborn non-renewable resource, so consideration of this constraint has been ignored and it is considered in non-renewable resource constraint, which completely discussed in sample problems posed for this proposed problem [4].

According to the definition of dual-resource constraint which mentioned before [4], some items had been considered such as project budget. If the project finance won't be available at the beginning of the project, and some amount of the budget will be allotted to the managers periodically, in this case, the project budget is a kind of dual-resource. On the one hand it's a non-renewable resource since the project budget has a specific amount and it will be finished; on the other hand it must be considered a renewable resource because some amount of it is available in each period. So for each bi-resource in this proposed problem, two more renewable & non-renewable constraints must be considered, which is also completely described in sample problems posed for this proposed problem.

3. Proposed Algorithm to Solve the Proposed Problem

ICA (Imperialist Competitive Algorithm) is a method in the field of evolutionary computation which is used to find the optimum solution in different optimization problems. This algorithm represents an algorithm to solve the mathematical optimization problems with the use of mathematical modeling of the social-political evolution process. From the usage perspective, this algorithm is grouped with evolutionary optimization algorithms like genetic algorithms, ant colony optimization, simulated annealing and etc. like all algorithms of this group, ICA algorithm forms a basic set of probable answers. These basic answers are known as "chromosomes" in genetic algorithm, "particle" in particle swarm algorithm and "country" in ICA algorithm. ICA algorithm improves these basic answers (countries) gradually with a special method which will be discussed later, and finally will find the appropriate answer (desired country) for the optimization problem.

In the beginning, the steps of the applied algorithm are presented to solve the proposed RCPSP problem. The process of the algorithm for these kinds of problems is as follows:

Step 1: in this step, a series of possible orders considering the constraints (precedence consideration and resource constraint will be created).

The process is as follows: at first, for each project activity, a random number between 0 and 1 is produced. Then these random numbers are arranged and saved in a list. The sequence number of these activities are saved in another list.

Step 2: the results are arranged depending on their suitability and the first 10 results are chosen as imperialist countries. Then the normalized cost and power of an imperialist is defined by

(1)

(2)

Step 3: the normalized power of an imperialist is the portion of colonies that should be possessed by that imperialist. Then the number of colonies of an empire will be

(3)

Step 4: the best imperialist is saved in BestSol. The major circle of the algorithm, steps 5 to 7, is repeated for a specific number of times (here, the number of repetitions is the criteria to make the algorithm to stop).

Step 5: imperialists and their colonies are invoked. Colonies move toward imperialists on the basis of this formula

(4)

After the movement, if a colony is more powerful than its imperialist, the colony and the imperialist change their places.

Step 6: the operation in step 5 is done for all imperialists. The power of imperialists is calculated one more time. A pre-determined number of colonies go under the control of the most powerful imperialist.

Step 7: this is the last step. Imperialists are arranged depending on their suitability and the best imperialist is saved in bestSol.

4. The Results of the Proposed Imperialist Competitive Algorithm for MRCPSP

In this section, RCPSP problems with multi-mode (multi-state) activities are being considered. There are j10, j12, j14, j16, j18, j20 and j30 sets in the library of these problems. One more feature of MRCPSP problems is that beside the renewable resources, they have non-renewable resources as well.

Problems with names of c15, c21, m1, m2, m4, m5, n0, n1, n3, r1, r3, r4 and r5 can also be found among the standard MRCPSP problems which have some differences in the number of resources and activities. For instance, group c problems have 18 activities, 2 renewable resources and 2 non-renewable resources. Group m problems have also 18 activities, 2 renewable resources and 2 non-renewable resources. Group n0 problems have 14 activities and only 2 renewable resources and n1 problems have 18 activities, 2 renewable resources and 1 non-renewable resource, and n3 problems also have 18 activities with 2 renewable and 3 non-renewable resources. Group r problems also differs in the number of renewable resources in the way that r1 problems have 18 activities with 1 renewable and 2 non-renewable resources, r3 have 3 renewable and 2 non-renewable resources, r4 have 4 renewable and 2 non-renewable resources and r5 have 5 renewable and 2 non-renewable resources [6].

In this study, only group j problems have been used for comparison. Between group j problems, j10, j12, j14, j 20 and j30 problems has been used. These problems have 2 renewable and 2 non-renewable resources.

In the table (1), the average deviation from the best answers in j10 up to j20 problem series is calculated, which the optimum answer is available. So the average deviation from these optimum answers has been compared in the table (1), using the best and newest ever-applied algorithms, in which the proposed algorithm holds the 3^rd place in this study.

Table 1. Results ICO algorithm for MRCPSP problem

The second criteria which is evaluated in these kinds of problems is the percentage of the optimum answers and another one is the process time of the CPU, which has been evaluated in the table (2).

Table 2. Result CPU time for solving MRCPSP problem with ICO algorithm

5. The Results of the Proposed ICA for Solving the Proposed Problem

According to the fact that a bi-objective model has been developed for RCPSP problems in this study, at first a problem is solved as an instance in order to show the algorithm performance in producing parto answers in the form of figure (1). It is obvious from the chart that the algorithm could produce the suitable parto to solve this sample problem which the answers and diversity are desirably suitable.

Figure 1. Pareto Answers with ICO algorithm

The algorithm has been used to solve some bi-objective problems from the MRCPSP problems and results has been evaluated through 2 important criteria namely diversity and spacing metric to check the quality of the produced parto answers in multi-objective problems.

1- Diversity Criterion

Zitzler defined a specific measurement criterion in which the length of a diameter is measured. This diameter is the diameter of the space used by final value of the objects for parto answer set [12].

2- Spacing Metric criterion

It's another criterion for checking parto's charts. This criterion studies distance of the answers from each other in order to finds the distance between answers of one point with its nearest neighbor. This criterion could be considered either ordinarily or normalized. Formulas of each group are brought later.

6. Checking the Performance of the Proposed Algorithm from the Point of Evaluation Criteria with PSP Algorithm

According to the discussed criteria in previous section, the algorithm is being used to solve different MRCPSP problems and its results have been compared with PSO algorithm which the results of these two criteria are brought in the table(3). At the end, two algorithms are being evaluated from the aspect of problems' solving time. Results indicated satisfactory performance of the ICA algorithm.

Table 3. Compare ICO algorithm with PSO algorithm

7. Numerical Example for Showing ICA Algorithm Performance in Problem Solving

To show the algorithm performance better, we're using a sample example for step-by-step functionality of ICA algorithm.

Problem definition is stated in bee's algorithm section. So in this section, we'll only discuss about the functionality of ICA algorithm.

10 imperialist are being chosen at first. Propriety, power and number of colonies will be specified for each imperialist and brought in the table (4).

Table 4. Colonial power and the number of samples in problem solving

As it is obvious from the table, imperialist number 1 has the best propriety and owns the most colonies. This imperialist will be stored in BestSol as the best answer.

After that each colony changed toward its imperialist, the power of each imperialist will be calculated again and the best imperialist will be specified. The results are presented in the table (5).

Table 5. The best example of elegance in problem solving

As it is obvious, imperialist number 1 has the best propriety and the most empire power. So 10 weakest colonies will be added to the colonies of this imperialist. This imperialist will be stored in BestSol as the best result. In addition, as it is clear, empires 8, 9 and 10 fail, because the number of their colonies become zero.

This process will be repeated for a specific number of times. On more important criterion for this algorithm to stop is when there is only one imperialist and all other empires had fail.

8. Conclusions

In this paper, a bi-objective problem was suggested for MRCPSP problem series, and then MRCPSP problem series and a proposed problem were solved with ICA algorithm. Results of MRCPSP problem solution have compared with the newest algorithm used to solve these series of problems and the results of proposed problem have compared with PSO algorithm which the results indicated a successful performance of this algorithm to solve these kinds of problems. This algorithm can be used to solve other RCPSP problems in future researches.