# Payment Scheduling Problem with Multiple Modes for Activities to Maximize the Net Present Value of a Project

Authors: Somayeh Ghasedi; Behrouz Afshar-Nadjafi
Journal: Journal of Engineering
 (2021)

---

## Abstract

In this paper, the multimode payment scheduling project is studied, which aims to maximize the net present value (NPV) of a project by deciding on payments and the start times of its activities. The problem is formulated mathematically from the point of view of the selected contractor of the project. In the proposed model, a bonus and penalty structure is considered, in which the project’s activities can be performed through different execution modes. Another interesting feature of the developed model is the possibility of switching between the execution’s modes during the implementation of each activity, which can increase the NPV. Because of the proposed model’s computational complexity, two metaheuristic algorithms are developed to tackle the underlying problem. In order to evaluate the performance of the developed algorithms, a set of 108 test instances are solved, and the computational results confirm the applicability of the solving methodologies.


---

## Body

## 1. Introduction

Net present value (NPV) is among the standard methods to evaluate the economic aspects of the projects. Efficient management of financial currents has a key role in improving the benefits of any decision makings including those made in project management. Balanced decisions in multimode case of resource-constrained project scheduling have influential importance in NPV based objectives. In this version of project scheduling problems, each activity has several scenarios for implementation with different duration, cost, and resources to be accomplished. In such cases, when an activity needs to be finished sooner, more money and resources should be spent. By contrast, if it is possible to postpone an activity before the project’s deadline, the implementation cost can be reduced through reduction of the consuming resources. This flexibility in selection of the execution modes can be exploited to achieve maximum NPV.A survey on the literature of the project scheduling problem shows that despite a great deal of attention to minimizing the makespan of projects, the works on maximizing NPV of projects are rare. How to schedule a project to maximize the NPV has gone under study since 1970, where Russell tried to model the financial dimensions of project management to maximize a project’s financial currents. In that model, the problem was formulated as a nonlinear programming on activity-on-arc (AOA) network. Grinold sought to maximize transactions’ present value. It was found that a payment scheduling problem can be transformed into a linear program [1]. Russell employed present value maximization to optimize a linearly constrained nonlinear function and utilized a linear programming succession to solve the problem [2]. Russell studied project scheduling for net present value maximization based on resource limitations, cash inflows, and cash outflows. They incorporated 80 test instances to compare six heuristic scheduling strategies [3]. Kazaz and Sepil proposed a programming model to maximize the NPV of client’s financial currents. They considered a progress-based model for the financial currents [4]. Payment scheduling problem was studied by Ulusoy and Cebeli for the first time from both the employer and contractor’s point of view. They presented a two-loop genetic algorithm in which the exterior loop denotes the employer and the interior one denotes the contractor. Having decided on the amount of payment in the interior loop, the contractor schedules the activities to maximize the project’s NPV [5]. Dayanand and Padman studied a model to improve NPV from the viewpoints of both the employer and the contractor. They presented a two-step algorithm which determines a collection of payments at the first step to maximize the employer’s NPV, followed by the second step in which the activities are rearranged to improve the contractor’s NPV [6]. Mika et al. investigated multimode resource-constrained project scheduling by incorporating cash flow discounts. They sought to implement the net present value maximization of project’s cash flows. Furthermore, they proposed tabu search and simulated annealing for solving the problem [7]. Elazouni and Metwally employed a genetic algorithm (GA) for finance-based scheduling to obtain maximized project profits via financing and indirect cost minimization [8]. He and Xu studied the project payment scheduling from the employer’s viewpoint in which activities could be done separately and the goal was to maximize the employer’s NPV [9]. He et al. presented the multimode project payment scheduling in which activities can be executive separately and the goal was to determine the start time of the activities and prepayments to maximize the employer’s NPV at the project due date [10]. Ranjbar proposed an optimal solution procedure for the project scheduling problem with permitted tardiness and discrete time/resource tradeoffs under maximum net present value objective. They showed that the project costs could be diminished if the mode with the minimum duration of each activity has been selected [11]. Fathallahi and Najafi presented a model to deal with imposed uncertainties in projects with the aim of maximizing the project’s NPV. They assumed some uncertain parameters as fuzzy numbers in order to show the efficiency of using GA and SA algorithms in solving the problems [12]. Leyman and Vanhoucke investigated two problems with the constraints on capital, which result in positive cash balance for the intended project. This study aimed to maximize the NPV by assigning a negative or positive cash flow to the activities [13]. Nasrabadi and Mirzazadeh developed a model using Markovian inflationary conditions to minimize the expected present value of execution costs. In their study, unlike most of the previous studies, the inflation rate and cost of items in each cycle were considered continuous-time variables under a Markov process. The numerical example and sensitivity analysis showed that their model could be adopted for the real-life projects as an applicable approach [14]. Leyman and Vanhoucke in another study investigated the single and multimode resource-constrained project scheduling problem. They tried to present a new scheduling technique and general framework with the help of a genetic algorithm aiming at enhancing the net present value of the project. To evaluate the influence of their approach, the proposed technique was tested on several datasets. The final results highlighted the far-reaching impact of the data’s parameters on the project’s NPV [15]. Hassanpour et al. compared the performance of genetic algorithm (NSGA-II) and a new multiobjective imperialist algorithm called MOICA for solving a biobjective preemptive multimode resource-constrained project scheduling problem based on minimizing makespan and maximizing net present value. In the end, they proved the superiority of the proposed MOICA over NSGA-II in obtaining the more high quality solutions [16]. Farughi et al. considered the resources as renewable ones, unlike the past studies. They tried to maximize the net present value and project flexibility with the aim of minimizing the project’s completion time. The multiobjective simulated annealing algorithm (MOSAA) was selected to solve the suggested model. They found that the large scale problems need to be solved by considering the efficient performance of the suggested algorithm for four presented benchmark problems [17]. Alavipour and Arditi proposed a model for financing cost minimization via several financing alternatives. They introduced a working schedule with typical activity durations. The advantages of their model included lower financing expenses, preventing liquidated damage and project time extension, and an optimized financing schedule with a reduced number of essential activities [18]. Alavipour and Arditi developed an integrated profit maximization framework for expected profit maximization through cost-time trade-off evaluation, activity start time adjustment, financing cost minimization, and work schedule extension minimization. Their model demonstrated its efficiency for contractors to maximize profits [19]. Liang et al. presented a model considering stochastic activity durations in robust resource-constrained max-NPV project problem. Therefore, they used a composite robust scheduling model together with simulated annealing and tabu search to achieve the satisfactory solutions. Their approach provided them with reducing the chance of payment plan disruptions besides contributing to the notable performance of project scheduling [20]. Delgoshaeia et al. proposed a dynamic backward approach to enhance the remaining resource usage while carrying out the project. In this regard, they could maximize the net present value (NPV) in multimode resource-constrained project scheduling problem considering activity splitting. Their approach showed a considerable effect and flexibility of the backward approach to be utilized in real-world projects [21]. Zarei et al. proposed a mathematical model for the project schedule to find an optimal solution with the aim of maximizing the net present value and minimizing the project time. GA, SA, and PSO algorithms were selected to solve the proposed model. The best option to perform activities would be considered, which led to a balance between time and cost. GA algorithm showed a better performance compared to the other two algorithms. However, SA was preferable in terms of using less computational time to solve the problem [22].There are many works in the literature of project scheduling considering multiple modes for executing the activities. Hsu and Kim developed a priority rule heuristic algorithm for multimode resource investment problems [23]. Zhu et al. focused on a multimode problem with limited general resources [24]. Sabzehparvar and Seyed-Hosseini studied the model with several discrete modes with resource restrictions considering the prerequisite relationships to maximize and minimize the mode-dependent delays of the activities [25]. In another study, they proposed a model for multimode resource investment problem with mode-dependent time lags [26]. He et al. contributed to multimode project payment scheduling for maximizing contractor net present value under project deadline constraints. They developed a tabu search and simulated annealing heuristic algorithms. The latter was found to be promising in solving the instances of the problem [10]. Peteghem and Vanhoucke developed a problem considering multiple execution modes for each activity of the project. They utilized a bipopulation genetic algorithm to solve this multimode resource-constrained project scheduling problem (MRCPSP). They used two types of populations as well as an extended serial schedule generation scheme in order to minimize the finish time of activity. The final results proved the positive influence of the mentioned elements on the performance of the genetic algorithm [27].Azimi et al. studied multimode resource-constrained project scheduling with the aim of maximization of the net present value and minimization of makespan simultaneously. To solve this problem, they used an evolutionary algorithm named multiobjective particle swarm optimization (MOPSO) [28]. A mixed-integer formulation and a solution procedure based on simulated annealing were proposed by Afshar-Nadjafi for the multimode resource availability cost problem [29]. Qi et al. extended a modified version of particle swarm optimization including forward activity list for the multimode resource availability cost problem [30].Multimodal genetic algorithms (MMGAs) have been used by Pérez et al. to optimize the resource-constrained multiproject scheduling problem (RCMPSP) as an alternative approach instead of heuristics algorithms based on priority rules. This approach enabled managers to use the capability of this algorithm to select between suboptimal solutions [31]. Nemati-Lafmejani et al. developed a novel biobjective optimization model to deal with the multimode resource-constrained project scheduling problem (MRCPSP) together with the contractor selection (CS) problem. The final goal of their study was to minimize the total project cost and minimize project makespan. Therefore, 30 test problems of various sizes were solved with the help of two metaheuristic algorithms called a nondominated sorting genetic algorithm (NSGA-II) and multiobjective particle swarm optimization algorithm (MOPSO). The most worth-mentioning conclusion to be drawn was that the makespan of the project was curtailed by increasing the number of contractors, which could provide decision-makers with a wider range of flexible and applicable approaches [32]. Ehsanifar et al. suggested a model with the ability to perform activities under different executive modes. Their model aimed to minimize project completion time and maximize the cash flow of the project. They used simulating annealing and multiobjective particle swarm optimization (MOPSO) for solving the proposed model in which SA showed better performance in obtaining the solutions [33].Having a review of the project scheduling literature, we found many works on project scheduling problems with possibility of preemption for the activities. Chiu-Chi compared and evaluated the benefits and downsides of traditional project management and theory-of-constraints (TOC) in project management. They also introduced an augmented resource-constrained TOC project scheduling framework [34]. Józefowska et al. performed an advantage/disadvantage comparison of traditional and TOC project management and proposed a TOC project scheduling method under resource constraints [35]. Afshar-Nadjafi et al. presented multimode resource-constrained project scheduling problem (P-MRCPSP) to minimize the project’s makespan subject to mode changeability after preemption. He used simulated annealing (SA) algorithm to obtain a globally optimum solution. He concluded from the results of 480 test instances of the problem that mode change would be so influential in improving the optimal makespan of the intended project [36]. Delgoshaei et al. developed a method to address the long delay problem caused by resource overallocation in the project completion date. This being the case, they adopted a new forward programming heuristic to consider positive cash flow priority and activity ID rules simultaneously. Their model proved that the makespan would be increased by modifying the overallocated schedules [37]. Afshar-Nadjafi in another study developed the preemptive multimode resource-constrained project scheduling problem (P-MRCPSP), where mode changeability is allowed following preemption, to minimize makespan of the project. He used simulated annealing (SA) algorithm to deal with this problem and applied statistical method in order to determine the effect of the presented method on the problem. It turned out that mode change could be influential in reaching the optimal makespan of the project [38].As mentioned, in the past decades, there have been many studies on different management problems. From the point of view of activities, project management has several discrete modes based on prerequisite relations, the single or multimode executive conditions of activities, and the possibility of interruption of activities, and from the viewpoint of the objective function, the goal of a problem can comprise different goals for optimization. In the present study, it is decided to have the possibility of mode change during execution of the project.Herein, we assume that each activity can be split intentionally for resolving the resources’ conflicts. In addition, the project manager can take advantage of the multimodeness of the activities. More specifically, the planner can relax the uniqueness of the execution mode, which permits an activity to be restarted after preemption with a different mode than the initial mode. This may result in a better solution than the classic models because it relaxes some constraints, which in turn widens the solution space. In terms of activity preemption, it needs to be highlighted that although splitting the activities may culminate in a longer project’s makespan, it can increase the NPV of the project, which is the objective function considered in this research.The remainder of this paper is structured as follows. Section2 descries the optimization model. The solution procedures are presented in Section 3. The computational results are analyzed and reported in Section 4. Finally, Section 5 concludes the paper.


## 2. Model Description

From the contractor’s viewpoint, the project payment scheduling problem with a multimode execution structure for maximization of NPV happens at regular time intervals. Project activities management with one specific due date happens while considering the probability of interruption of the activities and changing the modes.We assume that the activities are numbered from 1 toI. Each activity has different execution modes (1, 2, …, i). The project is shown as an AON network in which the node set denotes the activities and the arc set represents the finish-to-start prerequisite restrictions between the activities. At each time instant, each activity is done according to one of its own execution modes. There is a limitation for each resource per time unit (day), which will result in delay if its usage is exceeded; in other words, there would be preemption in case of resource shortages. If an activity is interrupted the execution mode of that activity can be changed to resolve the resource balance. At the end of each time period, the accomplished percent of each performed activity at the mentioned period is calculated, and then the payment amount has resulted through cost, benefit, and the payment proportion.Payments are done at regular periods and there exists one payment at the reward and punishment system in which there is a due date for each activity. If the activity is done sooner, there is a reward for the days the activity is finished sooner than scheduled and, of course, there is a fine for any delay. The total cost can be achieved by calculating the employer’s payment to the contractor and also the benefit and cost of each daily activity. In NPV calculation, as the total costs and payments are evaluated in comparison to the first day of the project, money loses its value day by day; that is why the interest rate is used to find out the final value of cash currents.


### 2.1. Assumptions

(1)
Project network is an AON which is a directed digraph with multiple execution modes for each activity.(2)
Payments are done periodically and the last payment should be done while finishing the project.(3)
The project should be completed before its due date.(4)
The contract expenditure includes both the contractor’s total expenditure and his benefit.(5)
If there is preemption in activities, there can be a change in execution mode.(6)
Each activity in each day of the project can be executed by just one mode of the execution modes.(7)
All the parameters in each problem are deterministic.(8)
There is a due date for each activity.(9)
There is a certain amount of job to be accomplished for each activity.(10)
There is a reward and punishment system for completion of each activity.(11)
All the resources are renewable.


### 2.2. Parameters

wi: Workload of activity imi: Executive mode of activity iwimi: Performed amount of job by activity i if it is carried out according to mode mi (in each day).hi: Due date of activity iK: Number of paymentspk: Amount of payment kei: Bonus of activity i if it is carried out sooner than the due date.ei′: Penalty cost of activity i if it is carried out after the due date.α: Modification rateθ: Payment proportionε: Benefit marginD: Project due dateD′: Project completion timeT′: Payment intervalsT0: Payment time of day zero (at the beginning of the project in which we have no payment)The model:(1)Max NPV=∑K=1D′/T′PKe−αTK+PKe−αD′−∑K=1D′/T′−1e−αTK+∑i=1I∑mi=1M∑t=Tk−1TkCit⋅Ximit+e−αD′∑i=1I∑mi=1M∑t=D′/T′⋅T′+1D′Cit⋅Ximit+∑i=11ei∑t=EFihiOite−αhi−t−∑i=1Iei′∑t=hi+1LFiOite−αt−hi,subject to(2)Ximit+Ximi′t≤1;i=1,…,I,(3)∑t=EFILFIOit⋅t≤D′,(4)∑EFiLFiOit=1;i=1,…,I(5)∑K=1D′/TPK=PMAX;k=1,…,K,(6)PK≤θ1+ε∑i=1IWiTk−WiTk−1Wi∗Ci,k=1,…,D′T′,(7)∑i=1I∑mi=1MRiLmi−Ximit≤∑L=1LRL;t=1,…,D′,L=1,k,…,L,(8)∑ESiLFi∑MiMWimiXimit≥Wi,i=1,…,I,(9)∑t=1D′∑mi=1MWimi⋅Ximit≥W∑mjMXjMj;t+1∈ESi+1,LFj−1,(10)Ci=∑OD′∑miM∑L=1LRiL⋅Ximit⋅CL;i=1,…,I,(11)WiTk=∑t=Tk−1Tk∑mi=1MWimi⋅Ximit;k=1,…,K,i=1,…,I,(12)Cit=∑miM∑L=1LRiLmi⋅Ximit⋅CL;t=0,…,D′,i=1,…,I.TK: Payment time of kRiLmi: Amount of L resource needed for activity i if it is carried out in mode mi (in each day).Cit: Cost of the necessary resources to carry out activity i in t dayCL: Specific cost of each resource LCi: Total cost of the necessary resources to carry out activity i.RL: Renewable limit of resource L in each day. There is a limit for each resource during the whole project which cannot be exceeded.WiTk: Performed amount of job by activity i at the end of the payment time of kOi t = 1,if activityiis finished at timet=1,0,otherwise.EFi: Earliest finish time of the activity iLFi: Latest finish time of the activity iESi: Earliest start time of the activity i.


### 2.3. Objective Function and Constraints

Based on the abovementioned formulation, the optimization model of max NPV with a bonus penalty structure can be constructed from the perspectives of the contractor. In this model, the objective function represents the contractor’s NPV of the project. The NPV is the subtraction of all discounted costs associated with the project from the employer’s discounted payments to a contractor while considering the bonus and penalty structure of activities. The total costs include the costs of used resources in a project. Also, if an activity is done sooner, there is a bonus, and if it is finished later, there is a penalty for it. To calculate NPV of the contractor, the penalties are subtracted from the employer’s payments and then the bonuses are added to that.Equation (2) shows that the project activities are executed just in one of their executive modes per day and each activity cannot be done with more than one mode within a day. Equation (3) shows that the project is done before its deadline; D. Equation (4) calculates the finish point of each activity. Equation (5) represents the summit of payments. Equation (6) shows the value of each payment. Equation (7) guarantees that using each resource in the whole project has a specific restriction. Equation (8) specifies that each activity has work content and in order to fulfill one activity, it should reach its job content. Equation (9) denotes the prerequisite relationships in a network. Equation (10) shows the total cost of each activity in the project. Equation (11) denotes the performed job content in each activity at the end of each time period. Equation (12) represents the total cost of each activity in a time period.


## 2.1. Assumptions

(1)
Project network is an AON which is a directed digraph with multiple execution modes for each activity.(2)
Payments are done periodically and the last payment should be done while finishing the project.(3)
The project should be completed before its due date.(4)
The contract expenditure includes both the contractor’s total expenditure and his benefit.(5)
If there is preemption in activities, there can be a change in execution mode.(6)
Each activity in each day of the project can be executed by just one mode of the execution modes.(7)
All the parameters in each problem are deterministic.(8)
There is a due date for each activity.(9)
There is a certain amount of job to be accomplished for each activity.(10)
There is a reward and punishment system for completion of each activity.(11)
All the resources are renewable.


## 2.2. Parameters

wi: Workload of activity imi: Executive mode of activity iwimi: Performed amount of job by activity i if it is carried out according to mode mi (in each day).hi: Due date of activity iK: Number of paymentspk: Amount of payment kei: Bonus of activity i if it is carried out sooner than the due date.ei′: Penalty cost of activity i if it is carried out after the due date.α: Modification rateθ: Payment proportionε: Benefit marginD: Project due dateD′: Project completion timeT′: Payment intervalsT0: Payment time of day zero (at the beginning of the project in which we have no payment)The model:(1)Max NPV=∑K=1D′/T′PKe−αTK+PKe−αD′−∑K=1D′/T′−1e−αTK+∑i=1I∑mi=1M∑t=Tk−1TkCit⋅Ximit+e−αD′∑i=1I∑mi=1M∑t=D′/T′⋅T′+1D′Cit⋅Ximit+∑i=11ei∑t=EFihiOite−αhi−t−∑i=1Iei′∑t=hi+1LFiOite−αt−hi,subject to(2)Ximit+Ximi′t≤1;i=1,…,I,(3)∑t=EFILFIOit⋅t≤D′,(4)∑EFiLFiOit=1;i=1,…,I(5)∑K=1D′/TPK=PMAX;k=1,…,K,(6)PK≤θ1+ε∑i=1IWiTk−WiTk−1Wi∗Ci,k=1,…,D′T′,(7)∑i=1I∑mi=1MRiLmi−Ximit≤∑L=1LRL;t=1,…,D′,L=1,k,…,L,(8)∑ESiLFi∑MiMWimiXimit≥Wi,i=1,…,I,(9)∑t=1D′∑mi=1MWimi⋅Ximit≥W∑mjMXjMj;t+1∈ESi+1,LFj−1,(10)Ci=∑OD′∑miM∑L=1LRiL⋅Ximit⋅CL;i=1,…,I,(11)WiTk=∑t=Tk−1Tk∑mi=1MWimi⋅Ximit;k=1,…,K,i=1,…,I,(12)Cit=∑miM∑L=1LRiLmi⋅Ximit⋅CL;t=0,…,D′,i=1,…,I.TK: Payment time of kRiLmi: Amount of L resource needed for activity i if it is carried out in mode mi (in each day).Cit: Cost of the necessary resources to carry out activity i in t dayCL: Specific cost of each resource LCi: Total cost of the necessary resources to carry out activity i.RL: Renewable limit of resource L in each day. There is a limit for each resource during the whole project which cannot be exceeded.WiTk: Performed amount of job by activity i at the end of the payment time of kOi t = 1,if activityiis finished at timet=1,0,otherwise.EFi: Earliest finish time of the activity iLFi: Latest finish time of the activity iESi: Earliest start time of the activity i.


## 2.3. Objective Function and Constraints

Based on the abovementioned formulation, the optimization model of max NPV with a bonus penalty structure can be constructed from the perspectives of the contractor. In this model, the objective function represents the contractor’s NPV of the project. The NPV is the subtraction of all discounted costs associated with the project from the employer’s discounted payments to a contractor while considering the bonus and penalty structure of activities. The total costs include the costs of used resources in a project. Also, if an activity is done sooner, there is a bonus, and if it is finished later, there is a penalty for it. To calculate NPV of the contractor, the penalties are subtracted from the employer’s payments and then the bonuses are added to that.Equation (2) shows that the project activities are executed just in one of their executive modes per day and each activity cannot be done with more than one mode within a day. Equation (3) shows that the project is done before its deadline; D. Equation (4) calculates the finish point of each activity. Equation (5) represents the summit of payments. Equation (6) shows the value of each payment. Equation (7) guarantees that using each resource in the whole project has a specific restriction. Equation (8) specifies that each activity has work content and in order to fulfill one activity, it should reach its job content. Equation (9) denotes the prerequisite relationships in a network. Equation (10) shows the total cost of each activity in the project. Equation (11) denotes the performed job content in each activity at the end of each time period. Equation (12) represents the total cost of each activity in a time period.


## 3. Heuristic Solution Procedures

Genetic algorithm (GA) has been used frequently to solve scheduling problems due to its effectiveness and efficiency in exploring solution space for complex problems. GA can work on a collection of feasible solutions at any given time. This is why it can go through a bigger space in a shorter time.The algorithm is started with a set of solutions (represented by chromosomes) called population. Solutions from one population are taken and used to form a new population (generation). This is motivated by the hope that the new population will be better than the old one by inheriting good features from the parent population. Solutions that are selected to form new solutions (offspring) are selected according to their fitness—the more suitable they are, the more chances they have to reproduce.Simulated annealing is a method for finding a good (not necessarily perfect) solution to an optimization problem. If you are in a situation where you want to maximize or minimize some function, your problem can likely be tackled with simulated annealing. This algorithm is among the most powerful algorithms to face the combinatorial optimization problems and this is why it is selected to solve our model.


### 3.1. Solving the Problem with GA Algorithm

#### 3.1.1. Choosing Chromosome

The number of project activities is shown byI and the vector length of the chromosome is assumed to be 2I. Each chromosome is divided into two divisions with length I and the members of the first part of the chromosome represent the activities and the members of the second part show the number of executive modes.


#### 3.1.2. Generating Initial Population of Chromosomes

Producing chromosomes of the initial population or generation is randomly performed to start the algorithm.Consider matrixi. “i” shows the number of activity. Activities are shown while considering their prerequisite relationships in a matrix. If “i” is the prerequisite of j, matrix space will be filled. Now, we act as the following to choose the primary sequence of the activities.Step 1:All the activities should be put on a list called activity list.Step 2:Consider a collection called S-list which includes activities which can be performed based on precedence relations. This collection is empty at first at the start of the algorithm.Step 3:We consider another collection named M-list, which includes all the activities which can be at any stage and can be executed.Finally, we call the arranged list of activities a sequence. Then, the activities are emitted from the activity list, while considering the prerequisite relationships, and after that, they are added to M-list. Through producing a random number, the activities in M-list are emitted and then put in the sequence list. In this method, the sequence of the activities is in a way that we can have a proper sequence and, therefore, chromosomes. A detailed structure of the proposed algorithms is depicted in Figures1 and 2.Figure 1
Conceptual flowchart of optimization process by GA.Figure 2
Conceptual flowchart of optimization process by SA.


#### 3.1.3. Fitness

Herein we evaluate the fitness value of each chromosome in the population. With the use of the fitness function’s value, we can calculate each chromosome’s probability and its cumulative probability to find the best chromosome. After the production of one generation of the initial population, it is time to have the genetic operator of crossover and mutation. Before the crossover and mutation operator, evolution operations are performed on chromosomes. First, chromosomes are put in an ascending order based on the fitness value. A percent of the new generation population comprises the best chromosomes of the previous generation. Having arranged the chromosomes, the best chromosomes are directly transferred to the new generation based on the fitness value. The chromosomes transferred through evolution are transferred based on the defined evolution probability (1−Pc−Pm). The achieved answers out of the elite orientation are used in order to have the crossover and mutation operators.


#### 3.1.4. New Population

Create a new population by repeating following steps until the new population is completed.


#### 3.1.5. Selection

Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected). Selecting parent chromosomes for the crossover is done with roulette wheel. We calculate the cumulative function probability on value for each chromosome and then make a random number between zero and one to have roulette wheel. The generated random number is adapted to the cumulative probabilities of selected chromosome and then we choose the parent chromosome adapted to the random number to have the crossover operator. The other parent chromosome should be chosen the same way, too. It should be added that if the chosen adapted number is put between two cumulative probabilities by roulette wheel, the higher cumulative probability is chosen. Parents are calledP1 and P2.


#### 3.1.6. Applying the Operators

In the above algorithm, the chromosomes include two parts. The first part is the sequence of activities and the second part shows the executive modes. The crossover operator is applied to the first part of the chromosome and the mutation operator is applied to the second part of it, and they both produce children as the new answers.(1) Crossover. At first, it is applied to the first part of parent chromosomes with probability of (Pc) and then the mutation operator is applied to the second part of chromosomes with the probability of (Pm). The crossover operator combines the features of the two parent chromosomes to produce two children who have the qualities of their parents. The crossover operators are one of the most important genetic algorithm operators and performing the algorithm correctly is really dependent on the proper designing of the crossover operator. Chromosomes are chosen in pairs and each pair changes into an intersect operator with the probability of (Pc) which results in the production of two children. In this algorithm, one-point crossover is used to choose parent chromosome and the roulette wheel is used for the crossover.Firstly, in order to avoid the production of improper children, the first part of parent chromosomes, point 1 to cutting point, is copied in the child’s chromosome. Now, we search all the copied activities of the first two parents in the second parent and omit them in the second parent. Then, the remaining activities of the second parent are copied in the first child in a succession similar to that of the second parent from cutting point toI.(2) Mutation. With a mutation, probability mutates new offspring at each locus (position in chromosome). The chromosomes in the above problem have two I parts. Therefore, in order to finally produce the children, the operator should be applied to the second part of chromosome. The mutation operator is the selective operator applied to the second part of chromosome; roulette wheel is used to choose chromosomes to have a mutation. The second parts of chromosomes are the modes to execute the activities. Later, the mutation operator is applied to the second part of a chromosome.I + 1 spaces relate to the executive mode of the first activity, I + 2 is for the operational mode of the second activity, and I + 1 is related to the executive mode of activity, all of which have the mutation operation, too. The mutation operator is applied to the modes, and if we face the infeasibility chromosome, we will randomly choose one executive mode out of the present operational mode for the specific activities.


#### 3.1.7. Accepting

Place new offspring in a new population. Each time the algorithm produces a new generation of answers and then achieves the new answers through applying the elitism operators of crossover and mutation.


#### 3.1.8. Replace

Use the newly generated population for a further run of the algorithm. The new population will be better than the old one, which is selected for a further run of the algorithm.


#### 3.1.9. Test

If the end condition is satisfied, stop and return the best solution in current population. The needed condition to end the genetic algorithm in the above problem is considered to be the number of generations. Each generation has better answers compared to the previous one because each time the best is transferred to the next generations or we can produce a child through combining the best chromosomes of parents. When the condition to end the algorithm is met, the optimum answer is achieved which is the best succession of activities with the executive modes at the beginning of the project to have the highest amount of NPV for the contractor and to solve the management problem.


#### 3.1.10. Loop

If the condition is not fulfilled, go to step 3.1.5.


### 3.2. Solving the Problem with SA Algorithm

To choose chromosome in this method is similar to GA algorithm. Project activities equalI and the vector length of the chromosome is 2I. Each chromosome is divided into I parts. The members of part one are the activities and the members of part two show the number of executive modes for each activity. First, we enter the primary parameters and then perform them while considering the condition of stopping the algorithm during the described steps.SA algorithm parametersStarting temperature (Ts)Iterations at each temperature (Rc)Predetermined cooling rate (0 <a < 1)SA algorithm stop conditionWe defined the condition of algorithm stop (ts/1000) which is a counter as the function of temperature. First, we produce a proper answer under the initial temperature and then calculate the value of objective function according to the primary chromosome.SA algorithm operation steps are as follows.Step 1:Primary temperature (Ts), the number of repetitions in each temperature (Rc), predetermined cooling rate (0 < α < 1), and (Shomar = 0) as a counter are entered.Step 2:Now we determine the present temperature (Tt=Ts) and the amount of objective function (NPV0).Step 3:Now we determine the present temperature asTt, and the present repetitive number R = 0. Later, we enter Shomar and the primary answer (initial chromosome) and the amount of objective function (NPV0).Step 4:We produce a neighborhood chromosome out of the initial chromosome and calculateNPV1 according to the new answer.Step 5:If△NPV=NPV1−NPV0<0, we accept the new chromosome as the better answer, shower = 0 and NPV0=NPV1; now go to 6. If not, we choose a random number between Zero and One.IfR≤eΔNPV/Tt , we accept the new chromosome as the better answer (accepting the worse answer), Shomar = Shomar + 1 and NPV0=NPV1; go to 6. If not, we reject the new chromosome (new neighborhood) and choose the previous answer as the superior answer up to that time. NPV0=NPV1 = and Shomar = Shomar + 1 and now go to 6.Step 6:Print Shomar and if Shomar <ts/1000, go to 7; if not go to 9.Step 7:NowR = R + 1. If R≤Rc, go to step 4. If not, go to step 8.Step 8:Tt=α⋅Tt; go to step 3.Step 9:Print Shomar and Render the achieved results and offer the best answer of NPV.After frequent and defined repetitions which are a function of temperature, if no better condition is achieved for NPV, we stop the algorithm and then the best answer up to that time is given as the optimum answer.Chromosome’s state of being proper is another important consideration. If one activity is a prerequisite for the next activity, it cannot be a proper candidate to produce new neighborhood ones, because if it is exchanged by each of the next activities which are not the prerequisite, it will be called improper in its next first activity due to being a prerequisite.The flowcharts of optimization process by SA and GA algorithms are shown in Figures1 and 2.


## 3.1. Solving the Problem with GA Algorithm

### 3.1.1. Choosing Chromosome

The number of project activities is shown byI and the vector length of the chromosome is assumed to be 2I. Each chromosome is divided into two divisions with length I and the members of the first part of the chromosome represent the activities and the members of the second part show the number of executive modes.


### 3.1.2. Generating Initial Population of Chromosomes

Producing chromosomes of the initial population or generation is randomly performed to start the algorithm.Consider matrixi. “i” shows the number of activity. Activities are shown while considering their prerequisite relationships in a matrix. If “i” is the prerequisite of j, matrix space will be filled. Now, we act as the following to choose the primary sequence of the activities.Step 1:All the activities should be put on a list called activity list.Step 2:Consider a collection called S-list which includes activities which can be performed based on precedence relations. This collection is empty at first at the start of the algorithm.Step 3:We consider another collection named M-list, which includes all the activities which can be at any stage and can be executed.Finally, we call the arranged list of activities a sequence. Then, the activities are emitted from the activity list, while considering the prerequisite relationships, and after that, they are added to M-list. Through producing a random number, the activities in M-list are emitted and then put in the sequence list. In this method, the sequence of the activities is in a way that we can have a proper sequence and, therefore, chromosomes. A detailed structure of the proposed algorithms is depicted in Figures1 and 2.Figure 1
Conceptual flowchart of optimization process by GA.Figure 2
Conceptual flowchart of optimization process by SA.


### 3.1.3. Fitness

Herein we evaluate the fitness value of each chromosome in the population. With the use of the fitness function’s value, we can calculate each chromosome’s probability and its cumulative probability to find the best chromosome. After the production of one generation of the initial population, it is time to have the genetic operator of crossover and mutation. Before the crossover and mutation operator, evolution operations are performed on chromosomes. First, chromosomes are put in an ascending order based on the fitness value. A percent of the new generation population comprises the best chromosomes of the previous generation. Having arranged the chromosomes, the best chromosomes are directly transferred to the new generation based on the fitness value. The chromosomes transferred through evolution are transferred based on the defined evolution probability (1−Pc−Pm). The achieved answers out of the elite orientation are used in order to have the crossover and mutation operators.


### 3.1.4. New Population

Create a new population by repeating following steps until the new population is completed.


### 3.1.5. Selection

Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected). Selecting parent chromosomes for the crossover is done with roulette wheel. We calculate the cumulative function probability on value for each chromosome and then make a random number between zero and one to have roulette wheel. The generated random number is adapted to the cumulative probabilities of selected chromosome and then we choose the parent chromosome adapted to the random number to have the crossover operator. The other parent chromosome should be chosen the same way, too. It should be added that if the chosen adapted number is put between two cumulative probabilities by roulette wheel, the higher cumulative probability is chosen. Parents are calledP1 and P2.


### 3.1.6. Applying the Operators

In the above algorithm, the chromosomes include two parts. The first part is the sequence of activities and the second part shows the executive modes. The crossover operator is applied to the first part of the chromosome and the mutation operator is applied to the second part of it, and they both produce children as the new answers.(1) Crossover. At first, it is applied to the first part of parent chromosomes with probability of (Pc) and then the mutation operator is applied to the second part of chromosomes with the probability of (Pm). The crossover operator combines the features of the two parent chromosomes to produce two children who have the qualities of their parents. The crossover operators are one of the most important genetic algorithm operators and performing the algorithm correctly is really dependent on the proper designing of the crossover operator. Chromosomes are chosen in pairs and each pair changes into an intersect operator with the probability of (Pc) which results in the production of two children. In this algorithm, one-point crossover is used to choose parent chromosome and the roulette wheel is used for the crossover.Firstly, in order to avoid the production of improper children, the first part of parent chromosomes, point 1 to cutting point, is copied in the child’s chromosome. Now, we search all the copied activities of the first two parents in the second parent and omit them in the second parent. Then, the remaining activities of the second parent are copied in the first child in a succession similar to that of the second parent from cutting point toI.(2) Mutation. With a mutation, probability mutates new offspring at each locus (position in chromosome). The chromosomes in the above problem have two I parts. Therefore, in order to finally produce the children, the operator should be applied to the second part of chromosome. The mutation operator is the selective operator applied to the second part of chromosome; roulette wheel is used to choose chromosomes to have a mutation. The second parts of chromosomes are the modes to execute the activities. Later, the mutation operator is applied to the second part of a chromosome.I + 1 spaces relate to the executive mode of the first activity, I + 2 is for the operational mode of the second activity, and I + 1 is related to the executive mode of activity, all of which have the mutation operation, too. The mutation operator is applied to the modes, and if we face the infeasibility chromosome, we will randomly choose one executive mode out of the present operational mode for the specific activities.


### 3.1.7. Accepting

Place new offspring in a new population. Each time the algorithm produces a new generation of answers and then achieves the new answers through applying the elitism operators of crossover and mutation.


### 3.1.8. Replace

Use the newly generated population for a further run of the algorithm. The new population will be better than the old one, which is selected for a further run of the algorithm.


### 3.1.9. Test

If the end condition is satisfied, stop and return the best solution in current population. The needed condition to end the genetic algorithm in the above problem is considered to be the number of generations. Each generation has better answers compared to the previous one because each time the best is transferred to the next generations or we can produce a child through combining the best chromosomes of parents. When the condition to end the algorithm is met, the optimum answer is achieved which is the best succession of activities with the executive modes at the beginning of the project to have the highest amount of NPV for the contractor and to solve the management problem.


### 3.1.10. Loop

If the condition is not fulfilled, go to step 3.1.5.


## 3.1.1. Choosing Chromosome

The number of project activities is shown byI and the vector length of the chromosome is assumed to be 2I. Each chromosome is divided into two divisions with length I and the members of the first part of the chromosome represent the activities and the members of the second part show the number of executive modes.


## 3.1.2. Generating Initial Population of Chromosomes

Producing chromosomes of the initial population or generation is randomly performed to start the algorithm.Consider matrixi. “i” shows the number of activity. Activities are shown while considering their prerequisite relationships in a matrix. If “i” is the prerequisite of j, matrix space will be filled. Now, we act as the following to choose the primary sequence of the activities.Step 1:All the activities should be put on a list called activity list.Step 2:Consider a collection called S-list which includes activities which can be performed based on precedence relations. This collection is empty at first at the start of the algorithm.Step 3:We consider another collection named M-list, which includes all the activities which can be at any stage and can be executed.Finally, we call the arranged list of activities a sequence. Then, the activities are emitted from the activity list, while considering the prerequisite relationships, and after that, they are added to M-list. Through producing a random number, the activities in M-list are emitted and then put in the sequence list. In this method, the sequence of the activities is in a way that we can have a proper sequence and, therefore, chromosomes. A detailed structure of the proposed algorithms is depicted in Figures1 and 2.Figure 1
Conceptual flowchart of optimization process by GA.Figure 2
Conceptual flowchart of optimization process by SA.


## 3.1.3. Fitness

Herein we evaluate the fitness value of each chromosome in the population. With the use of the fitness function’s value, we can calculate each chromosome’s probability and its cumulative probability to find the best chromosome. After the production of one generation of the initial population, it is time to have the genetic operator of crossover and mutation. Before the crossover and mutation operator, evolution operations are performed on chromosomes. First, chromosomes are put in an ascending order based on the fitness value. A percent of the new generation population comprises the best chromosomes of the previous generation. Having arranged the chromosomes, the best chromosomes are directly transferred to the new generation based on the fitness value. The chromosomes transferred through evolution are transferred based on the defined evolution probability (1−Pc−Pm). The achieved answers out of the elite orientation are used in order to have the crossover and mutation operators.


## 3.1.4. New Population

Create a new population by repeating following steps until the new population is completed.


## 3.1.5. Selection

Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected). Selecting parent chromosomes for the crossover is done with roulette wheel. We calculate the cumulative function probability on value for each chromosome and then make a random number between zero and one to have roulette wheel. The generated random number is adapted to the cumulative probabilities of selected chromosome and then we choose the parent chromosome adapted to the random number to have the crossover operator. The other parent chromosome should be chosen the same way, too. It should be added that if the chosen adapted number is put between two cumulative probabilities by roulette wheel, the higher cumulative probability is chosen. Parents are calledP1 and P2.


## 3.1.6. Applying the Operators

In the above algorithm, the chromosomes include two parts. The first part is the sequence of activities and the second part shows the executive modes. The crossover operator is applied to the first part of the chromosome and the mutation operator is applied to the second part of it, and they both produce children as the new answers.(1) Crossover. At first, it is applied to the first part of parent chromosomes with probability of (Pc) and then the mutation operator is applied to the second part of chromosomes with the probability of (Pm). The crossover operator combines the features of the two parent chromosomes to produce two children who have the qualities of their parents. The crossover operators are one of the most important genetic algorithm operators and performing the algorithm correctly is really dependent on the proper designing of the crossover operator. Chromosomes are chosen in pairs and each pair changes into an intersect operator with the probability of (Pc) which results in the production of two children. In this algorithm, one-point crossover is used to choose parent chromosome and the roulette wheel is used for the crossover.Firstly, in order to avoid the production of improper children, the first part of parent chromosomes, point 1 to cutting point, is copied in the child’s chromosome. Now, we search all the copied activities of the first two parents in the second parent and omit them in the second parent. Then, the remaining activities of the second parent are copied in the first child in a succession similar to that of the second parent from cutting point toI.(2) Mutation. With a mutation, probability mutates new offspring at each locus (position in chromosome). The chromosomes in the above problem have two I parts. Therefore, in order to finally produce the children, the operator should be applied to the second part of chromosome. The mutation operator is the selective operator applied to the second part of chromosome; roulette wheel is used to choose chromosomes to have a mutation. The second parts of chromosomes are the modes to execute the activities. Later, the mutation operator is applied to the second part of a chromosome.I + 1 spaces relate to the executive mode of the first activity, I + 2 is for the operational mode of the second activity, and I + 1 is related to the executive mode of activity, all of which have the mutation operation, too. The mutation operator is applied to the modes, and if we face the infeasibility chromosome, we will randomly choose one executive mode out of the present operational mode for the specific activities.


## 3.1.7. Accepting

Place new offspring in a new population. Each time the algorithm produces a new generation of answers and then achieves the new answers through applying the elitism operators of crossover and mutation.


## 3.1.8. Replace

Use the newly generated population for a further run of the algorithm. The new population will be better than the old one, which is selected for a further run of the algorithm.


## 3.1.9. Test

If the end condition is satisfied, stop and return the best solution in current population. The needed condition to end the genetic algorithm in the above problem is considered to be the number of generations. Each generation has better answers compared to the previous one because each time the best is transferred to the next generations or we can produce a child through combining the best chromosomes of parents. When the condition to end the algorithm is met, the optimum answer is achieved which is the best succession of activities with the executive modes at the beginning of the project to have the highest amount of NPV for the contractor and to solve the management problem.


## 3.1.10. Loop

If the condition is not fulfilled, go to step 3.1.5.


## 3.2. Solving the Problem with SA Algorithm

To choose chromosome in this method is similar to GA algorithm. Project activities equalI and the vector length of the chromosome is 2I. Each chromosome is divided into I parts. The members of part one are the activities and the members of part two show the number of executive modes for each activity. First, we enter the primary parameters and then perform them while considering the condition of stopping the algorithm during the described steps.SA algorithm parametersStarting temperature (Ts)Iterations at each temperature (Rc)Predetermined cooling rate (0 <a < 1)SA algorithm stop conditionWe defined the condition of algorithm stop (ts/1000) which is a counter as the function of temperature. First, we produce a proper answer under the initial temperature and then calculate the value of objective function according to the primary chromosome.SA algorithm operation steps are as follows.Step 1:Primary temperature (Ts), the number of repetitions in each temperature (Rc), predetermined cooling rate (0 < α < 1), and (Shomar = 0) as a counter are entered.Step 2:Now we determine the present temperature (Tt=Ts) and the amount of objective function (NPV0).Step 3:Now we determine the present temperature asTt, and the present repetitive number R = 0. Later, we enter Shomar and the primary answer (initial chromosome) and the amount of objective function (NPV0).Step 4:We produce a neighborhood chromosome out of the initial chromosome and calculateNPV1 according to the new answer.Step 5:If△NPV=NPV1−NPV0<0, we accept the new chromosome as the better answer, shower = 0 and NPV0=NPV1; now go to 6. If not, we choose a random number between Zero and One.IfR≤eΔNPV/Tt , we accept the new chromosome as the better answer (accepting the worse answer), Shomar = Shomar + 1 and NPV0=NPV1; go to 6. If not, we reject the new chromosome (new neighborhood) and choose the previous answer as the superior answer up to that time. NPV0=NPV1 = and Shomar = Shomar + 1 and now go to 6.Step 6:Print Shomar and if Shomar <ts/1000, go to 7; if not go to 9.Step 7:NowR = R + 1. If R≤Rc, go to step 4. If not, go to step 8.Step 8:Tt=α⋅Tt; go to step 3.Step 9:Print Shomar and Render the achieved results and offer the best answer of NPV.After frequent and defined repetitions which are a function of temperature, if no better condition is achieved for NPV, we stop the algorithm and then the best answer up to that time is given as the optimum answer.Chromosome’s state of being proper is another important consideration. If one activity is a prerequisite for the next activity, it cannot be a proper candidate to produce new neighborhood ones, because if it is exchanged by each of the next activities which are not the prerequisite, it will be called improper in its next first activity due to being a prerequisite.The flowcharts of optimization process by SA and GA algorithms are shown in Figures1 and 2.


## 4. Computational Results

The function of the two metaheuristic algorithms (GA and SA) is compared and studied through different tests. To do such tests, we require defining some proper problems. Obviously, setting the algorithm parameters has a direct relation with its efficiency; this is why Taguchi method is used to regulate the parameters.


### 4.1. Assumptions and Setting of GA Parameters

In this algorithm, the initial population is randomly produced as big as the pop size. Random move and crossover are used as operators. The algorithm is stopped after a certain repetition (generation). Therefore, the algorithm has four parameters called probability crossing, probability mutation, population size (pop size), and generation number (generation). In Tables1–5, the operators and parameters along with their levels are given.Table 1
Taguchi’s orthogonal arrays matrix (GA).
RunABC1A(1)B(1)C(1)2A(1)B(2)C(2)3A(1)B(3)C(3)4A(2)B(1)C(2)5A(2)B(2)C(3)6A(2)B(3)C(1)7A(3)B(1)C(3)8A(3)B(2)C(1)9A(3)B(3)C(2)Table 2
Operators, parameters, and their levels (GA).
FactorSymbolLevelTypeTempASmall problemsB(1) = 10, B(2) = 20, B(3) = 30Medium problemsB(1) = 40, B(2) = 50, B(3) = 60Large problemsB(1) = 80, B(2) = 100, B(3) = 120RepeatBSmall problemsC(1) = 0.6, C(2) = 0.7, C(3) = 0.8Medium problemsC(1) = 0.7, C(2) = 0.8, C(3) = 0.9Large problemsC(1) = 0.7, C(2) = 0.8, C(3) = 0.9αCSmall problemsC(1) = 0.05, C(2) = 0.07, C(3) = 0.09Medium problemsB(1) = 0.05, B(2) = 0.07, B(3) = 0.09Large problemsB(1) = 0.05, B(2) = 0.07, B(3) = 0.09Table 3
Optimum levels of GA parameters in small size instances.
FactorSymbolOptimal levelPop sizeBA2=20(Pc)BB2=0.7pmBC2=0.07Table 4
Optimum levels of GA parameters in medium size instances.
FactorSymbolOptimal levelPop sizeBA2=50(Pc)BB2=0.8pmBC2=0.07Table 5
Optimum levels of GA parameters in large size instances.
FactorSymbolOptimal levelPop sizeBA2=100(Pc)BB2=0.8pmBC2=0.07


### 4.2. Assumptions and Arranging or Setting SA Parameters

In this algorithm, we consider a hypothetical value for temperature based on previous studies (Initial TEMP = 200000). The algorithm is stopped after a certain repetition (T/1000) and it has three parameters called initial temperature (TEMP), repetition in each temperature (Repeat), and temperature decrease coefficient (α). In Tables 6–10, the operators and parameters along with their levels are given.Table 6
Taguchi’s orthogonal arrays matrix (SA).
RunABC1A(1)B(1)C(1)2A(1)B(2)C(2)3A(1)B(3)C(3)4A(2)B(1)C(2)5A(2)B(2)C(3)6A(2)B(3)C(1)7A(3)B(1)C(3)8A(3)B(2)C(1)9A(3)B(3)C(2)Table 7
Operators, parameters, and their levels (SA).
LevelFactorSymbolTypeSmallTempAA(2) = 100000RepeatB(2) = 15αC(3) = 0.99MediumTempBA(2) = 500000RepeatB(2) = 30αC(3) = 0.99LargeTempCA(2) = 1500000RepeatB(2) = 50αC(3) = 0.99Table 8
Optimum levels of SA parameters in small size instances.
FactorSymbolOptimal levelTempAA2=100000RepeatBB2=15αCC3=0.99Table 9
Optimum levels of SA parameters in medium size instances.
FactorSymbolOptimal levelTempBA2=500000RepeatBB2=30αCC3=0.99Table 10
Optimum levels of SA parameters in large size instances.
FactorSymbolOptimal levelTempBA2=200000RepeatBB2=50αCC3=0.99In this study, the performance of the proposed methods is evaluated by two indicators, which are NPV and solving time. Comparing the results of doing tests on solution algorithms, the tables and graphs show the average function evaluation of GA and SA algorithm in three groups called small, medium, and large groups (each problem is performed five times).To compare the two presented algorithms, 108 sample problems were produced and each of the mentioned problems was solved using genetic and simulated annealing algorithms. The sample problems were given in three groups called small, medium, and large. The achieved results are shown in Figures3–8 through two algorithms.Figure 3
Comparison chart of net present value obtained by GA and SA algorithms in small problems.Figure 4
Comparison chart of net present value obtained by GA and SA algorithms in medium problems.Figure 5
Comparison chart of net present value obtained by GA and SA algorithms in large problems.Figure 6
Comparison the outcomes of running time of small size algorithm between GA and SA algorithms.Figure 7
Comparison the outcomes of running time of medium size algorithm between GA and SA algorithms.Figure 8
Comparison the outcomes of running time of large size algorithm between GA and SA algorithms.As can be seen, the genetic algorithm has achieved much better answer in comparison to simulated annealing algorithm at 100 percent of the cases. Further as the time needed to solve problems by SA algorithm was so close to that of GA algorithm in most problems and even in some problems, solving them by SA algorithm was much more time-consuming, and the achieved answers through genetic algorithm seemed better and finally resulted in higher NPV for the contractor. In general, it can be concluded that genetic algorithm has better answers than SA at the same given time to solve problems.To show GA algorithm quality compared to SA algorithm in all problems, the 2-samplet-test with the certainty level of %95 (a = 0.05) is given to compare NPV. The variance of samples was considered equal and the quality of the achieved answers in all the three groups, small, medium, and large, seemed better by GA algorithm compared to SA, because the P value amount is larger than a = 0.05 recognition level. Therefore, the “Zero” hypothesis is accepted and the opposite one is rejected.In project scheduling problems, time-oriented and financial objectives have always been modeled as trade-off measures. In this paper, we tried to investigate the procedure, in which mode switching may increase projects profitability.


## 4.1. Assumptions and Setting of GA Parameters

In this algorithm, the initial population is randomly produced as big as the pop size. Random move and crossover are used as operators. The algorithm is stopped after a certain repetition (generation). Therefore, the algorithm has four parameters called probability crossing, probability mutation, population size (pop size), and generation number (generation). In Tables1–5, the operators and parameters along with their levels are given.Table 1
Taguchi’s orthogonal arrays matrix (GA).
RunABC1A(1)B(1)C(1)2A(1)B(2)C(2)3A(1)B(3)C(3)4A(2)B(1)C(2)5A(2)B(2)C(3)6A(2)B(3)C(1)7A(3)B(1)C(3)8A(3)B(2)C(1)9A(3)B(3)C(2)Table 2
Operators, parameters, and their levels (GA).
FactorSymbolLevelTypeTempASmall problemsB(1) = 10, B(2) = 20, B(3) = 30Medium problemsB(1) = 40, B(2) = 50, B(3) = 60Large problemsB(1) = 80, B(2) = 100, B(3) = 120RepeatBSmall problemsC(1) = 0.6, C(2) = 0.7, C(3) = 0.8Medium problemsC(1) = 0.7, C(2) = 0.8, C(3) = 0.9Large problemsC(1) = 0.7, C(2) = 0.8, C(3) = 0.9αCSmall problemsC(1) = 0.05, C(2) = 0.07, C(3) = 0.09Medium problemsB(1) = 0.05, B(2) = 0.07, B(3) = 0.09Large problemsB(1) = 0.05, B(2) = 0.07, B(3) = 0.09Table 3
Optimum levels of GA parameters in small size instances.
FactorSymbolOptimal levelPop sizeBA2=20(Pc)BB2=0.7pmBC2=0.07Table 4
Optimum levels of GA parameters in medium size instances.
FactorSymbolOptimal levelPop sizeBA2=50(Pc)BB2=0.8pmBC2=0.07Table 5
Optimum levels of GA parameters in large size instances.
FactorSymbolOptimal levelPop sizeBA2=100(Pc)BB2=0.8pmBC2=0.07


## 4.2. Assumptions and Arranging or Setting SA Parameters

In this algorithm, we consider a hypothetical value for temperature based on previous studies (Initial TEMP = 200000). The algorithm is stopped after a certain repetition (T/1000) and it has three parameters called initial temperature (TEMP), repetition in each temperature (Repeat), and temperature decrease coefficient (α). In Tables 6–10, the operators and parameters along with their levels are given.Table 6
Taguchi’s orthogonal arrays matrix (SA).
RunABC1A(1)B(1)C(1)2A(1)B(2)C(2)3A(1)B(3)C(3)4A(2)B(1)C(2)5A(2)B(2)C(3)6A(2)B(3)C(1)7A(3)B(1)C(3)8A(3)B(2)C(1)9A(3)B(3)C(2)Table 7
Operators, parameters, and their levels (SA).
LevelFactorSymbolTypeSmallTempAA(2) = 100000RepeatB(2) = 15αC(3) = 0.99MediumTempBA(2) = 500000RepeatB(2) = 30αC(3) = 0.99LargeTempCA(2) = 1500000RepeatB(2) = 50αC(3) = 0.99Table 8
Optimum levels of SA parameters in small size instances.
FactorSymbolOptimal levelTempAA2=100000RepeatBB2=15αCC3=0.99Table 9
Optimum levels of SA parameters in medium size instances.
FactorSymbolOptimal levelTempBA2=500000RepeatBB2=30αCC3=0.99Table 10
Optimum levels of SA parameters in large size instances.
FactorSymbolOptimal levelTempBA2=200000RepeatBB2=50αCC3=0.99In this study, the performance of the proposed methods is evaluated by two indicators, which are NPV and solving time. Comparing the results of doing tests on solution algorithms, the tables and graphs show the average function evaluation of GA and SA algorithm in three groups called small, medium, and large groups (each problem is performed five times).To compare the two presented algorithms, 108 sample problems were produced and each of the mentioned problems was solved using genetic and simulated annealing algorithms. The sample problems were given in three groups called small, medium, and large. The achieved results are shown in Figures3–8 through two algorithms.Figure 3
Comparison chart of net present value obtained by GA and SA algorithms in small problems.Figure 4
Comparison chart of net present value obtained by GA and SA algorithms in medium problems.Figure 5
Comparison chart of net present value obtained by GA and SA algorithms in large problems.Figure 6
Comparison the outcomes of running time of small size algorithm between GA and SA algorithms.Figure 7
Comparison the outcomes of running time of medium size algorithm between GA and SA algorithms.Figure 8
Comparison the outcomes of running time of large size algorithm between GA and SA algorithms.As can be seen, the genetic algorithm has achieved much better answer in comparison to simulated annealing algorithm at 100 percent of the cases. Further as the time needed to solve problems by SA algorithm was so close to that of GA algorithm in most problems and even in some problems, solving them by SA algorithm was much more time-consuming, and the achieved answers through genetic algorithm seemed better and finally resulted in higher NPV for the contractor. In general, it can be concluded that genetic algorithm has better answers than SA at the same given time to solve problems.To show GA algorithm quality compared to SA algorithm in all problems, the 2-samplet-test with the certainty level of %95 (a = 0.05) is given to compare NPV. The variance of samples was considered equal and the quality of the achieved answers in all the three groups, small, medium, and large, seemed better by GA algorithm compared to SA, because the P value amount is larger than a = 0.05 recognition level. Therefore, the “Zero” hypothesis is accepted and the opposite one is rejected.In project scheduling problems, time-oriented and financial objectives have always been modeled as trade-off measures. In this paper, we tried to investigate the procedure, in which mode switching may increase projects profitability.


## 5. Conclusion

This paper proposes the use of metaheuristic algorithm to solve project scheduling problems with activities along with the possibility of preemption and change mode with a bonus penalty structure. The problem has complexity in calculation time, and in other words, it is classified as NP-hard problems. In this research, genetic metaheuristic algorithm and simulated annealing algorithm were used for optimized scheduling. In order to compare the two presented algorithms, 108 sample problems were studied in this paper. The performance of the procedures was tested on an available test set, which shows genetic algorithm is more efficient than simulation annealing at the given time. For further research, it is recommended that studying the other metaheuristic algorithms can be considered to develop the desired model. Furthermore, there should be a model to discuss the problem from the viewpoints of both the contractor and employer. This is just the multiobjective model which can focus on maximizing NPV, resource restriction, and minimizing the project time.



---

*Source: 2354105-2021-03-25.xml*