Journal of Industrial Engineering, University of Tehran, Special Issue, 2011, PP. 51-60 51

Resource-Constrained Scheduling of Construction Projects Using the Harmony Search Algorithm

Yaghob Gholipour*1 and Mohammad Mehdi Shahbazi 2

School of Civil Engineering, College of Engineering, University of Tehran,

Tehran, Iran

Engineering Optimization Research Group, College of Engineering, University of Tehran, Tehran, Iran

(Received 20 November 2010, Accepted 2 May 2011)

Abstract

During the implementation, construction projects usually encounter situation that considerably affects the project scheduling and cost. This study aims at using an improved version of the harmony search algorithm (HSA) to schedule resource constrained construction projects. This model is formulated as a global optimization problem. It will determine the duration of each activity to minimize the project total cost. The algorithm tries to find the best duration for each activity so that it leads to the total consumption of the corresponding resource. This may cause some activities to start simultaneously. The improvements have been made to increase the convergence rate and to lower the cost and shorten duration of the project. A numerical example has been proposed to evaluate the efficacy of the algorithm. This algorithm also addresses issues such as multi-resource, resource combination, and resource limit. Two scenarios have been considered for the test problem. The former scenario shows the project scheduled using the minimum duration list and the latter scenario schedules the project using the optimization algorithm. A comparison between the two scenarios shows the effectiveness of the proposed algorithm in decreasing the total cost and duration of the projects.

Keywords: Project scheduling, Project cost flow optimization, Construction projects, Cash flow management

Introduction

Regarding project scheduling, resource constraints are generally considered the most important issue for contractors. Researchers have devoted considerable time and energy to investigate this issue over the past decades. Since adequate cash flow management is directly related to cost control and profit margin for contractors, numerous techniques have been recently developed for cash flow purposes. Due to the size, discreteness and complexity of construction projects, ineffective scheduling and design can result in a disastrous outcome.

* Corresponding author: Tel: +98- 21- 61112804 Fax: +98- 21- 66461024 Email: [email protected]

In project scheduling, resources are utilized in accordance with activity requirement and implementation time relevant to the cash flow. In other words, the contractors are bound to follow a strict financial guideline to implement any phase of the project. Various financial factors, such as interest rate, payment condition, and credit limit, not only affect the project cost, but also influence the amount and timing of resource usage. Woodworth and Shanahan [1] have shown that time-oriented schedules usually exceed the targeted completion time by an average of around 38%. This is due to the fact that the successful completion of any activity is not only time but also resource dependent. The general resource-constrained project scheduling problem (RCPSP) arises when a set of interrelated activities (precedence relations) are given and when each activity can be performed. Questions arise regarding which resource-duration mode should be adopted, and when each activity begins in order to optimize the project cost. Slowinski and Weglarz [2] proposed a backtracking algorithm for solving duration minimization and net present value (NPV) maximization problem in a precedence and resourceconstrained network. Maximizing the NPV of a project was first suggested by Russell [3]. Grinold [4] observed that a simple variable substitution, converts Russell’s formulation into an equivalent linear program. Neumann and Zimmermann [5] extended Grinold’s algorithm to problems with generalized precedence. Elmaghraby and Herroelen [6] proposed an approximate solution procedure to the NPV maximization problem, while Schwindt and Zimmermann [7] developed an exact method based on the steepest ascent principle. Some efforts has been made to apply meta-heuristic algorithms to project scheduling optimization. Lucko [8] employed simulated annealing for optimizing cash flows, while Chen [9] has employed particle swarm algorithm. Geng et al. [10] presented an improved version of ant colony algorithm, which gives better results than the original version. Liao [11] presented the state of the art meta-heuristic algorithms for project scheduling.

1. Activities’ relationship Assume activity A1 is a predecessor of A2 and A3. If the resources are unconstrained, both A2 and A3 can begin simultaneously, as soon as A1 finishes. On the other hand, if there are not enough resources for both activities, one begins immediately and the other one would be delayed. This leads to a longer duration and larger project cost. The proposed algorithm, schedules the project based upon the activity relationships, resource constraints, and financial requirements.

In the proposed model, each activity can choose its own resource requirements and the corresponding duration. Activity duration di, is derived from a set of durations Di; moreover, for each activity, the set Di, consists of all possible durations complying with various resource requirement. This model provides schedulers with options to chose the best resource-duration mode considering the activities relationship. The finish-start (FS) relationship, which is typically used for construction projects, is shown as Eq. (1).

S i S i di ;i 1,2,,P

(1) i i, A;di Di

where Si denotes start time of activity i; Si’ denotes the start time of activity i’, which succeeds activity i; P represents last activity in the project network; di is the duration of activity i; A denotes the set of pairs of activities with precedence relationships; and Di represents the set of all eligible duration for activity i.

2. Resource usage

A common feature of all heuristics is that they assign a resource-duration mode to each activity. For longer activity duration, there is the possibility that parallel activities may begin simultaneously.

The solution we discussed in this research distributes resources among activities so that they would start at the same time and progress in parallel until the resources are totally depleted. The total duration time in this case, may be shorter than the sum of the duration time of all activities if they were not started in parallel. As shown in Figure 1, the required resources decreases, when the duration of d2 and d3 increases. Consequently, the resource usage can be controlled to optimally fit the constraints. Eq. (2) summarizes requirements of resource type Rj on day k.

SEk

k , i 1 Rij RL j(2)

iSE k ;k 1,2,,T ;j 1,2,,J

where Rij represents the required resource for type j and activity i during di; RLj denotes the limit of resource type j per day; SEk is the set of in progress activities on day k; T denotes project duration; and J is the number of resource types. Resources available for completing tasks can be classified as either renewable or non-renewable. Renewable resources typically have the same amount of availability in every period for an unlimited number of periods, while non-renewable resources are depleted after a certain amount of consumption (or number of periods). In a real construction project, both resource types are employed. For this research we are considering the later type.

3. Project cost flow

Minimizing project duration often carries with it simultaneous increase in project net present value. In other words, early completion of any activity, implies early cash payments. This generally will result in an increase in the amount of net present value [2]. The model formulation complies with the financial terminology employed by Elazouni and Metwally [12] and Au and Hendrickson [13], where payments for the completed activities are made at the end of each period. Typical cash out flows on a construction project include interest, material, labor cost, etc. [14]. Numerous approaches have been developed to investigate the cash flow in construction projects. Barbosa and Pimentel [15] constructed a linear programming model for cash flow management in the Brazilian construction industry. Chiu and Tsai [16] developed a heuristic searching rule to gain a near-optimal solution and incorporated penalty and bonus into the multi-project scheduling problems with a discounted cash flow. Elazouni and Gab-Allah [17] applied integer programming to establish a financebased scheduling model for minimizing project duration, and presented project schedules with various credit limits. Elazouni and Metwally [12] considered credit limit and scheduled a construction project using improved genetic algorithms for total profit maximization under different credit limit settings. A project schedule, which does not consider cash flow, will overlook the costs associated with interest and payment conditions, and may lead to budget overruns and project failure [14]. In this research, only cash out flows have been considered in calculation of project cost that is equal to the sum of the payments during construction, including the cost of each resource on each day. Regarding the payment for each resource Pjk, Eqs. (3) and (4) show the total daily cost flow and total payment at period t, respectively.

J

Pk Pjk (3)

1

m

Pt Pk (4)

1

where Pk denotes the total payment of direct cost on day k for resource j; J is the number of resources; Pt denotes the total payment at the end of period t; and m is number of days per period. Eq. (6) shows the overall expenses at the end of period t (Et), which consists of DCk, the total direct cost on day k; Et is summarized expense during period t; Ot is expenses of overheads, mobilization costs, taxes, and bonus at period t; and It is the interest charges at the end of period t. Eq. (7) shows the interest charges for each period. As for Eq. (7), it calculates interest until period t-1 and approximates the interest from the end of period t-1 to period t, which is generated from direct costs and other expenses during period t.

m

Et DC k Ot

k 1 (5)

Et Et It (6)

R It R N t 1

Et

2 (7)

t 1;k 1,2,,T

where R represents the interest rate per period; and Nt is the net cash out flow including interest charges at the end of period t. The cumulative cash out flow at the end of period t (Ft) is presented in Eq. (8), and the relationship among net cash out flow, cumulative cost flow, and total payment is as Eq. (9).

Ft N t 1 Et (8)

N t 1 Ft 1 Pt 1 (9)

t 1,2,…,L

where Ft denotes the cumulative cash out flow including interest charges at the end of period t; Nt-1 is net cash out flow including interest charges at the end of period t-1; Et is summarized expense during period t; and Pt-1 denotes the total payment at the end of period t-1; and L is the last period in the project. Minimizing net cash out flow (NL) without considering cash inflow, will lead to maximizing profit. Net cash out flow is considered at the end of last period of the project, L, and the objective is to minimize the net cash out flow at the last period, NL, defined by Eq. (10)

Minimizef d( ) N L

d i D ii , 1,2,…,n

Subject to SEk (10)

k , Rij RL j

i 1

iSE k ;k 1,2,,T ;j 1,2,,J

where f(d) is the objective function; di is optimization variable (duration of activity i); Di is the set of possible range of ith activity duration; and n is the number of decision variables.

4. Optimization algorithm

Many approaches, such as meta-heuristic algorithms (genetic algorithm, neural networks, etc.), mathematical programming, and CP can be employed to address resource-constrained scheduling problems. Meta-heuristic algorithms focus on solving problems in a short time, and provide approximate solutions. At times they can be imprecise and user dependent. Mathematical programming and CP techniques are applied to find an exact solution. Compared with mathematical programming, CP is not restricted by any particular model formulation, such as linear equations [18], and has been widely and successfully applied to complex problems, such as scheduling problems in various fields [19, 20]. As mentioned above, the proposed algorithm prolongs the activity durations to reach the optimum resource usage and minimum project cash out flow. An improved version of HS is employed here to find the optimum duration for each activity.

The original Harmony Search (HS) algorithm is a replication of a musical performance process. A musician’s search to find a better state of musical harmony (a perfect state) [21] is similar to optimization process that seeks to find a global solution (a perfect state) as determined by an objective function. The pitch of each musical instrument determines the aesthetic quality; similarly, the set of values assigned to each decision variable determines the value of the objective function. The original HS algorithm consists of the following steps:

Initializing the optimization problem and algorithm parameters: The parameters of HS algorithm, that is, HMS, HMCR, and PAR are also specified at this step. The Harmony Memory Size (HMS) is the number of solution vectors in the Harmony Memory (HM) and Harmony Memory Considering Rate (HMCR) and Pitch Adjusting Rate (PAR) are parameters that are used to improve the solution vector. HM is a memory location where all the solution vectors (sets of decision variables) are stored which is similar to the genetic pool in GA.

Initializing HM: HM matrix shown in (11) is filled with as many solution vectors as the value of HMS. These solutions are randomly generated and sorted according to the values of the objective function, f(d).

HM d1,d 2,,d HMS (11)

Improvise a new harmony from HM: Memory considerations and pitch adjustments determine if the new harmony vector d (d d1, 2,,d n) should be generated from HM. That is, di (the value of ith variable for the new vector) is chosen from values in HM or Di .The value of HMCR which varies between 0 and 1 will determine where to choose the possible new value as indicated by Eq. (12).

d d d1,2,…,d HMS HMCR

d i iiii (12)

d i Di1 HMCR

The HMCR is the probability of choosing one value from the stored values in HM and (1-HMCR) is the probability of randomly choosing one feasible value, di, not limited to those stored in the HM. For example, a HMCR of 0.95 indicates that the HS algorithm will choose the duration of ith activity from stored values in the HM with a 95% probability and from the entire feasible range with a 5% probability. A HMCR value of 1.0 is not recommended because of the possibility that the solution may be improved by values not stored in the HM. This is similar to the reasoning for using mutation rate in the selection process of Genetic Algorithm. Every component of the new harmony vector, d (d d1, 2,,d n) is examined to determine whether it should be pitch-adjusted. This procedure uses the PAR parameter that sets the rate of adjustment for the pitch chosen from the HM as shown in Eq. (13).

YESw p. .PAR

di (13)

Now p. .1PAR

The pitch adjusting process is performed only after a value is chosen from the HM. The value (1-PAR) implies doing nothing. A PAR of 0.3 indicates that the algorithm will choose a neighboring value with

30%HMCR probability. The HMCR and PAR parameters introduced in Harmony Search help the algorithm find globally and locally improved solutions.

Update the HM: The new harmony vector replaces the worst solution if a better objective function value is obtained. HM is then resorted.

Check if the termination criterion is satisfied: When the termination criterion is not satisfied steps 3 and 4 are repeated.

HS preserves the history in HM vectors similar to that of Tabu Search and is able to change the adaptation rate (HMCR) through out the computation period, which resembles Simulated Annealing. It also considers several vectors simultaneously in a manner similar to GA. However, the major difference between GA and HS algorithm is that the latter generates a new vector from all the existing vectors (all harmonies in HM), while GA generate a new vector from only two of the existing vectors (parents). For further information about the HS algorithm, see Refs [21-26]. Figure 2 illustrates the procedure of HS algorithm. An improvement has been applied to the original algorithm. In this improvement, Di is confined in each step according to the last result as shown in Eq (14), Numerical studies shows the effectiveness of this improvement.

Di (Di1,Di2)

Di1 max{di

d ,di*}

2 (14)

Di2 min{di

d ,Di n }

2

d 2,4,6,;diDi

where Δd is the eligible duration range which should be an even integer value; di* is the minimum eligible duration of activity i according to the resource constraints; Din is the upper bound of eligible activity duration list Di; di is the duration of activity i assigned in the previous step; and the d’i is the new duration of activity i chosen randomly from the list D’i.

Project profit has been defined as the sum of all expenditures (direct costs and other expenses) and payments for completed activities. Cost flow minimization at the last period, L, leads to the profit maximization of the project. The enumeration procedure starts with the activities scheduled to complete with feasible resource and precedence with left-shifted or early finish times. It examines right-shifting activities in later time periods to permit examination of the resource and objective function trade offs that occur during such scheduling construction with the constraints as shown in Eqs. (1) and (2). The advisable point of the HS algorithm is to find a project schedule, which is close to the d* (i.e. a vector containing the minimum possible activity durations).

procedure

5. Computational experiment

To evaluate the performance of the proposed algorithm in detail, two computational experiment has been conducted. In both examples,

Di={1,2,…,50}; Δd=4; It=0.01; and HMS=10 are assumed as the initial values. Numerical experiments showed that HMCR=0.50 and PAR=0.90 lead to better results.

5.1. Case study 1

This case is a small project, which contains nine activities and seven resources. It is presented here to show how the algorithm works. Tables Error! Reference source not found. and Error! Reference source not found. show the activities and resources of forming and pouring concrete of a roof, respectively. Figure 3 shows the corresponding activity-on-node (AON) diagram, in which each node shows an activity Ai and its duration di (i=1,2,…,p). The resource requirements and predecessors are shown in Error! Reference source not found..

Table 1: Form and pouring concrete of the first roof: definition of activities and resource requirements for case study 1

Activity Description Predecessors di* Resources

A1 Strip column forms – 1 2R2

A2 Install rebar of the main beams A1 5 12R2,5R3,0.4R4

A3 Forming the beams A2 6 6R1,8R2,0.2R4

A4 Install secondary beams A2 2 6R2,0.6R4

A5 Putting the roof blocks A3,A4 3 6R2,800R5

A6 Install rebar of the roof A5 2 5R2,0.5R3,0.5R4

A7 Install stages A5 2 6R2

A8 Pour roof slab A6,A7 5 8R2,2R4,48R7

A9 Cure roof slab A8 1 3R2,R4,4R6

Table 2: Form and pouring concrete of the first roof: definition of resources and costs for case study 1

Resource Description Constraint Cost

R1 Rough carpenter crew 1 25

R2 Labor crew 4 18

R3 Rebar 1 Ton 800

R4 Engineer 1 30

R5 Roof block 300

Pieces 0.60

R6 Water 10 m3 0.20

R7 Concrete 10 m3 50

Two scenarios have been considered here. Scenario 1 schedules the project using the least possible duration di* (Eq. (15) and Error! Reference source not found.).

*RL j

73763074954

d i max{j 1,2,, }J (15)

Rij where RLj is the limit of resource type j; di* is the least duration of activity i; Rij is the required resource type j for activity i; and J is the number of resource types. An interest rate of It=0.01 is assumed for both scenarios. For scenario 1, the total cost was obtained Cost1=9566 units. Figure 4 shows the corresponding Gantt chart.

Scenario 2 is the optimal schedule obtained from the proposed algorithm, which schedules the project with Cost2=9456 units. Figs 4 and 5 show the corresponding Gantt chart diagram of scenarios 1 and 2, respectively. Although the algorithm increased the duration of activities A4, A6, and A7, but the total cost and duration decreased. This demonstrates the efficiency of the algorithm.

Figure 6 shows the convergence diagram of the improved algorithm in comparison to the original algorithm. The convergence rate for the proposed algorithm is has been greatly improved.

Figure 6: Convergence diagram of the improved algorithm in comparison to the original algorithm

– Example 1

5.2. Case study 2

This case is based on a real construction project, which shows the efficiency of the algorithm in large and real projects. It is containing 32 activities and 7 resources. Error! Reference source not found. and Figure 7 show the project definition and obtained results. It should be noticed that the improvement has a better influence on larger and more complex projects.

Table 3: Project definition and result of original and improved HS algorithm for case study 2

Activity Description Predecessors

Predecessors

d

i

*

d

i

*

d

i

(

OriginalHS

)

قیمت: تومان