Dear Label_Name,

Greetings! I hope you are well.

I am writing on behalf of an international publishing house, Science and Education Publishing, USA (http://www.sciepub.com).

Science and Education Publishing (SciEP) is a multidisciplinary open access publisher of Journals covering the fields of Science, Technology and Medicine. All SciEP publications are subject to high-quality peer review, editorial and production processes and are freely available online.

Welcome to the April, 2013 edition of SciEP newsletter, providing monthly summaries of articles on science & education related topics of interest to scientist and professionals. The mission of our journals is to provide an open access forum for publishing new findings on issues pertinent to scientific and academic field. We also invite you to submit original research papers, review articles, short reports, or case studies are considered for publication in our Multidisciplinary Journals.

American Journal of Public Health Research
DOI: 10.12691/ajphr-1-1-3

The Implementation of a Tele-Homecare System with Service Oriented Architecture and HL7 Message Transmission Standard
Ching-Sung Wang

American Journal of Medical and Biological Research
DOI: 10.12691/ajmbr-1-1-2

The Influence of Ethanol on Pyruvate Kinases Activity in Vivo, in Vitro, in Silico
Lelevich Sergey Vladimirovich, Khrustalev Vladislav Victorovich, Barkovsky Eugene Victorovich, Shedogubova Tatyana Aleksandrovna

American Journal of Medical Sciences and Medicine
DOI: 10.12691/ajmsm-1-1-1

Clinical and Histological Features in Wegener Granulomatosis
Li Cavoli Gioacchino, Passantino Rita, Bono Luisa, Tortorici Calogera, Ferrantelli Angelo, Giammarresi Carlo, Rotolo Ugo

American Journal of Infectious Diseases and Microbiology
DOI: 10.12691/ajidm-1-1-2

The Curse of Lymphatic Filariasis: Would the Continual Use of Diethylcarbamazine Eliminate this Scourge in Papua New Guinea?
Anne Lanham, Lillian Mwanri

We have released issues of some journals on February 2013.
American Journal of Public Health Research
American Journal of Medical Sciences and Medicine
American Journal of Medical and Biological Research
American Journal of Pharmacological Sciences
American Journal of Clinical Medicine Research
American Journal of Nursing Research
American Journal of Cancer Prevention
American Journal of Medicine Studies
American Journal of Infectious Diseases and Microbiology
American Journal of Cardiovascular Disease Research
American Journal of Biomedical Research
American Journal of Mechanical Engineering
American Journal of Microbiological Research
Journal of Preventive Medicine
American Journal of Food and Nutrition
American Journal of Hypertension Research
American Journal of Sports Science and Medicine
Journal of Cancer Research and Treatment
American Journal of Zoological Research
Journal of Biomedical Engineering and Technology
American Journal of Microbiological Research
Biomedical Science and Engineering

We are pleased to announce that submissions are now being accepted for peer review for all the journals across all our subject areas in SciEP.

Please submit your manuscript via our online submission system:
http://www.sciepub.com/author/signin

To unsubscribe from our mailing list, please click on the following link: unsubscribe

I am looking forward to hearing from you.

Kind regards,

David Rain
Email:join@sciepub.com
Science and Education Publishing (http://www.sciepub.com)

Discrete Time-Cost Tradeoff Model for Optimizing Multi-Mode Construction Project Resource Allocation

Shuangshuang Nie*, Jihong Gao

Department of Construction Management, Tongji University, Shanghai, China

Abstract: The project scheduling and resource allocation problems have been studied using different optimization methods. The resource leveling problem was proposed to reduce the resource fluctuation and was always studied independently resource constraint problem. For example, resource-constrained project scheduling problem (RCPSP) was proposed to optimize scheduling under resource constraints. This research proposed a new model which integrates the resource leveling problem and resource-constrained time-cost tradeoff problem. The evolutionary multi-objective optimization technique, strength Pareto evolutionary approach II (SPEA II) was applied to calculate the Pareto front of time and cost. The resource leveling measured by the metric, resource release/re-hiring, was converted to resource cost. The analysis of the time complexity of the model showed that the runtime of the algorithm was polynomial times of the number of activities. The results of case testing showed that the model was reasonably accurate in comparison with a proposed baseline model.

Keywords: project scheduling, resource-constrained project scheduling problem, resource leveling, genetic algorithm, optimization, strength pareto evolutionary approach II

Received June 6, 2015; Revised July 5, 2015; Accepted August 18, 2015

Citation: Shuangshuang Nie, Jihong Gao, Discrete Time-Cost Tradeoff Model for Optimizing Multi-Mode Construction Project Resource Allocation. American Journal of Civil Engineering and Architecture, 3 (3A). 9-16. January 2015. doi:10.12691/ajcea-3-3A-2

1. Introduction

In building industry, simulation has been used to solve building design and construction. For example, a variety of building design tool has been proposed to improve the building design performance. Two problems should be considered in the integration of information system. One is how to solve the problems of information exchange and the other is the content of information, hierarchy and flow that information system needs to integrate [1].

During the construction phase, project resources are allocated according to site constraint and project schedule. However, the widely used critical path method (CPM) does not consider resource availability. Resource-constrained project scheduling problem (RCPSP) was proposed to optimize scheduling under resource constraints. RCPSP was defined from three aspects of characteristics: resource environment; activity characteristics; and objective function [2].

The RCPSP can be further divided into the single-mode and the multi-mode RCPSPs in terms of the number of modes in which resources are used or consumed. Simulation has been used to solve building design and construction problem. When the activity durations become variable in different modes, the combination of different modes generates varied costs. In this sense, the RCPSP may be evolved into a discrete time-cost tradeoff problem, which can be subdivided into the deadline problem and the budget problem [3]. The deadline problem is to minimize resource cost within the limit of the maximum project duration while the budget problem is to minimize the project duration within a maximum cost [4].

The methods for solving the discrete time-cost tradeoff problem are mainly divided into two categories: exact algorithms and heuristic algorithms. Since the RCPSPs are combinatorial problems in nature, the exact algorithms, such as branch and bound algorithm, use mathematical programming to find the optimum solutions [5]. However, the exact algorithms are inefficient in the case of relative large projects with many activities or variables because the time-cost tradeoff is a NP problem that is hard to solve [6]. Simulation approach has been used to solve this problem. Simulation is not a new method for construction and has been already used to evaluate the project performance (e.g, design and scheduling), building control system [7,8], and building design [9,10,11]. Due to the nature of the NP problem, the simulation runtime is relatively long in order to find the optimum solution. Therefore, some surrogate based methods can be used to find the optimum solutions. For example, Hu and Shen used surrogate model that was constructed by sampling points adaptively and generating approximation surfaces with fast computing time. The model can evaluate the influence of different risk factors of building energy usage [12].

Optimization methods such as genetic algorithms (GAs) and neural networks were applied to solve the building design and project scheduling problems [13,14]. The objective function were usually set to minimizing the project duration [2,15,16,17]. The chromosome representation of GAs could be permutation based, priority rule based and priority value. Serial and parallel scheduling techniques were adopted to convert the chromosome into the actual schedule [18,19].

The time-cost tradeoff problem can be divided into two types: continuous and discrete. The second type is also a sub-problem of the RCPSP. Early researches did not consider resource constraints when developing GA based approaches to solve time-cost tradeoff problems [20,21]. In recent years, some researchers tried to investigate multi-mode discrete time-cost tradeoff using GAs [22,23,24].

Resource fluctuation is mainly studied in the scope of the resource leveling problem, which describes the process of reducing the fluctuations in resource usage over the project duration. Undesired resource fluctuation may cause inefficient and costly implementation of construction, for example, frequently rehiring and releasing workers, lowering productive level and interruption of learning curve effects [25], incurring indirect costs for training cost of new workers [26]. These implicit costs incurred by undesired resource fluctuations may account for a large amount of resources costs. Exact methods and heuristic methods were used to solve this problem [26]. However, the exact methods are still inefﬁcient for addressing projects with a larger number of activities. Heuristic algorithms, such as particle swarm optimization (PSO) and GA were adopted to solve leveling problems under different circumstances [25,26,27]. The algorithms search possible locations of noncritical activities to smooth the resource usage. The objective is usually to achieve uniform resource consumption. However, the resource leveling metrics proposed in these models measured and penalized the difference between ﬂuctuating resource consumption and a predefined desirable shape [25]. Alternative shapes of resource proﬁles which may have more efficient resource utilization may be penalized. Thus, in El-Rayes and Jun [25], the authors developed two innovative metrics without predetermining the shape of the resources, release and re-hire (RRH) and resource idle days (RID). The RRH metric can be useful when the release and rehire of resource are allowed in projects while the RID metric may be used where additional idle resources are required to kept on site during low demand periods.

Resource leveling and resource-constrained project scheduling problems are inherently interrelated. A certain schedule having a higher resource cost may have a lower resource fluctuation. However, the two problems were usually studied independently [28]. Only a few integrated models were developed to solve two problems simultaneously [29]. In Chan and Chua [30], authors presented a commercial GA package Genesis which was formulated to consider both the problems. The objective was to minimize the deviations of required resources from the available resource proﬁles. Resource leveling was addressed by calculating the resource underutilization and overutilization. Hu and Flood [2] developed an integrated scheduling method to minimize the project duration and resource fluctuation by using the strength Pareto evolutionary approach II (SPEA II) which outperformed several other multi-objective optimization techniques in solving the resource-constrained project scheduling problem. In [2,27], authors combined resource allocation and leveling by using a GA technique. The objective was to minimize the total project duration under resource constraints and the appropriate moments of selected resources important to resource leveling. In Leu and Yang [31], authors integrated time-cost tradeoff, resource constraint and resource leveling based on GA. The sum of the absolute differences between actual resource usage and average resource usage was used as a metric of measuring the resource leveling. The ideal resource profile was predefined as a rectangular shape. In Lucko [32] the authors used GA for optimizing linear scheduling project. Only project duration was address.

The literature review shows that PCPSP has not been fully explored in the integrated models. The researches mainly used a single objective function to minimize project duration, cost, or deviation between resource usage and the defined value. Resource leveling tended to be address in these models by adding a constraint. In addition, only single-mode RCPSP was integrated with the resource leveling problem. Therefore, this research aimed to develop a model that could solve the resource leveling problem and multi-mode RCPSP (more specifically, resource-constrained discrete time-cost tradeoff problems) simultaneously by using a multi-objective optimization technique in order to achieve the optimum solutions.

2. Problem Description

The mathematical description of the problem was defined in this section. The problem was defined from three characteristics: resource environment, activity characteristics and objective functions. Activities are subject to precedence constraint. The start time (ST) of an activity should be larger than the finish time (FT) of the preceding activities. dil denotes the duration of an activity i in a mode l. The total resource set K includes all the resource types of a project. The capacity of a resource type km ∈ K per time period is set to Rm. The quantity of resource m used by an activity i in a time period is riml if the activity is performed in a mode l.

The problem is solved based on a multi-objective optimization technique whose objective functions are to minimize the resource cost and the total project duration. The cost is split up to two parts: resource usage cost and resource fluctuation cost.

2.1. Resource Usage

The resource usage cost (RUC) is defined as the cost of resources used by all the activities in a given activity modes. For a multi-mode RCPSP, an activity may have different modes each of which would require varied duration and resource amount. RUC denotes the total resource cost in the project duration T (see Eqs. (1) and (2)). denotes the unit cost of the resource m. is used to calculated amount of resource m used at a particular time t. is equal to 1 if an activity i is performed at a time period t and o otherwise.

[picture] | (1)

[picture] | (2)

2.2. Resource Fluctuation

When resources are newly added or dismissed, additional costs will incur. Such costs may include training, transportation and bidding costs. El-Rayes and Jun [25] proposed two metrics: release and re-hire (RRH) and resource idle days (RID), to measure the level of the resource fluctuation. The RRH and RID are calculated using Eqs. (3) and (4) [25].

[picture] | (3)

[picture] | (4)

Where:

H=total increases in the daily resource demand;

T=total project duration;

rt = resource demand on day t;

MRD=maximum resource demand during the entire project duration.

The two metrics are agreeable though they are used in different circumstances. In this research, the metric of measuring the resource leveling RFC was calculated based on the metric RRH. RFC is calculated by Eq. (5). UHCm denotes the unit cost of hiring and releasing a resource type m and RRHm denotes the amount of a hired or increased resource m. The cost of MRD is alse added to the RFC to minimize the resource demand [2].

[picture] | (5)

3. Model development

Figure 1. Overview of the model

The model consists of four modules: the evolutionary multi-objective optimization (EMO), the project scheduling, the resource leveling and the local search modules (see Figure 1). The model begins and ends with the EMO module. The fitness values of the EMO are calculated based on time and cost fed into by the project scheduling and resource leveling modules. The local search module is to further optimize the results calculated by the EMO module.

3.1. Evolutionary Computing Model

This module searches the solution space to find the Pareto optimal. If the objective is to minimize Fi(x), a point (i.e., a solution), x’ X, is Pareto optimal if there does not exist another point, x X, such that F(x) F(x’), and Fi (x) <Fi (x’) for at least one function. This definition is illustrated in Figure 1. The objective functions are to minimize the F1 and F₂, and the solid dark points denote Pareto optimal (i.e., nondmoninated). The white points are non Pareto optimal (i.e., dominated) points because at least one dark points have larger values in terms of F₁ and F₂.

Figure 2. Illustration of Pareto optimal

SPEA II [33] was developed based on the natural evolutionary principle. SPEA II conducts crossover and mutation as shown in Figure 1. Unlike the single-objective GA algorithm, SPEA II uses the environmental selection scheme to preserve the Pareto optimal. Pareto-based ﬁtness assignment is used to identify nondominated vectors from the current population. The three high level goals are achieved in SPEA II [34].

(1) Preserving nondominated points at each generation.

(2) Generating the known Pareto front and determining the nondominated sets and converging to the true Pareto front.

(3) Generating a uniform distribution across the Pareto.

The line in Figure 2 can be imagined as a Pareto front line. The EMO algorithm needs to ensure known Pareto optimal is evenly distributed along the Pareto front line and to avoid cluster. SPEAII uses an external archive containing nondominated solutions previously found (Goal 1). Nondominated individuals are copied to the external nondominated set (see Figure 1). SPEA II has an enhanced archive truncation method that ensures to preserve the boundary solutions. The fitness assignment strategy and GA operations considers both closeness to the true Pareto front (Goal (2)) and even distribution of solutions (Goal (3)). The nondominated points are also preserved based on the fitness values.

Application of the SPEA II algorithm into this research requires specifying some parameters and variables. The following sections introduced methods of generating the initial population, calculating the fitness values, and defining crossover and mutation strategies.

3.1.1. Initial Population

The scheme of chromosome representation should be first defined before generating the initial population. There are three encoding methods: permutation based, priority value based and priority rule based methods [17]. Hartmann [35] applied permutation based encoding method into the multi-mode RCPSP. In the permutation based method, each individual is given by a sequence of activity. In the beginning, the dummy start activity is added into the schedule, and then each activity is added into the schedule with earliest start time according to the activity sequence specified by the individual. For priority value based methods, each activity is given by a unique priority value and each time a precedence feasible activity with the highest priority value is selected to add into the schedule. Both the permutation based and priority value based methods can the serial scheduling scheme to convert the chromosome to genotype (i.e., schedule).

Because this problem defined in this research has a broader scope than the classic RCPSP and the resource leveling module also needs to employ the gene representation, the priority based encoding approach was adopted.

The specific encoding approach is illustrated in Figure 3. The first section of chromosome denotes the priority values which are unique integers in the range from 1 to n (i.e., the total number of activities). The second section denotes the mode of activities. When the two sections are specified, chromosome gene values would be fed into the resource leveling module to generate genotype (i.e., schedule).

Figure 3. Chromosome structure of GA module

3.1.2. Fitness assignment

SPEA II calculated fitness using Eq (6) [33]. R(i) is the function of “strength” S(j) calculated by considering for each individuals that the number of individuals which it dominates to and that the number of individuals which it dominates. The values of S(j) can be derived from cost and project duration. SPEA II uses a nearest neighbor density estimation technique to calculate D(i) in the fitness values and to ensure the points are evenly distributes along the know Pareto front and to avoid cluster.

The fitness values of the nondominated individuals are less than 1.

[picture] | (6)

[picture] | (7)

[picture] | (8)

Where:

F(i) = Fitness value for solution i

R(i) = Raw fitness value calculated by summation of the strength values S(j) of all the individuals j that dominate the individual i. S(j) is equal to the number of individuals that the individual j dominates.

D(i) = Density estimator calculated by inverse of the distance to the k-th nearest neighbor

3.1.3. Crossover and Mutation Operations

The crossover method of the activity mode uses the standard crossover method. However, for the activity priority values, the standard one-point crossover method cannot be used because the priority values should be kept unique in different gene positions. The crossover method developed by Hartmann (1998) was adopted to implement the crossover operation of the first section of the chromosome. The method starts with selecting a random point in the parent chromosome. Then scan the parent genes to select unique priority values that do not exist in the child chromosome [17]. For instance, in Figure 4, the left part of the gene values in child 1 comes from parent 1 and the right part is from the parent 2 by left-to-right scan. The scan makes the right part of child 1 takes the first three gene values which are different from the left part of child 1. Similarly, the left part of child 2 takes genes from parent 2 and the right part of genes are taken from parent 1 by scanning different genes.

Figure 4. Crossover of the first section of a chromosome

The mutation of the priority values of activities is achieved by swapping two randomly selected genes in a chromosome. For the second section of the chromosome, the mutation operator modiﬁes modes at each position with an equal probability. If a position is selected, a random value within the range of the total number of modes is selected.

3.2. Project Scheduling Model

When the activity and mode lists are fed into the module. The schedule would be built up in the project scheduling module. Activities are scheduled according to the serial scheme scheduling approach [18]. Three activities sets are established, i.e., scheduled set, eligible set and decision set. At first, all the activities are placed in the decision set. The decision set contains all the activities to be scheduled. The scheduled activity set contains activities that have already been scheduled (i.e., starting and finishing time is determined).The activities whose precedent activities are scheduled and included in the scheduled set are then moved to the eligible set from the decision set. The eligible set contains all the activities that are allowed to be scheduled because the precedent activities have been added into the schedule chart. Several activities are moved to the eligible set simultaneously. Only the activity in the eligible set showing the largest priority value is selected to be moved to the scheduled set from the eligible set. This activity is added to the project schedule chart and the starting time is adjusted to meet the resource constraint. This process is repeated until all the activities in the decision set are moved to the schedule set. This whole process is also called the forward pass.

The above-mentioned process starts from the first activity. The resource and precedent constraints are kept feasible in this process. On the other hand, it is possible to start from the last dummy activity. An activity is moved from decision set to eligible set when its succeeding activities are added to the schedule set. This process is regarded as backward pass.

The last task is to calculate the total float (TF) for each activity. The following method is used: the backward pass is used to ensure the activities to finish as late as possible. Then, by deducting the latest finish time by the earliest finish time, the TF of each activity is then calculated. This process may lead to the change of the total project duration. The reason is that some activities are constrained not only by the precedence but also resource availability. Shifting an activity would possibly cause an activity in the critical path to become a noncritical activity. Therefore, the final project duration should be re-calculated at the end of the resource leveling module by deducting the finish time of the last dummy activity by the start time of the first dummy activity.

3.3. Resource Leveling Model

This module would calculate the time and cost needed by the fitness calculation of the EMO module. The first task is to adjust the noncritical activities (i.e., activities whose TF is larger than zero) to reduce the RFC. Where to locate these noncritical activities in the schedule is the critical work in the process of reducing RFC.

Reducing RFC can be done by the reduction of RRH + MDR. The noncritical activities were removed from the schedule and formed a noncritical activity list. In the subsequent steps, in terms of the priority values of the free activities, each activity will be added into a location where the maximum reduction of RRH + MRD should be achieved. After a noncritical activity is added to the schedule, the start and finish time of other noncritical activities are thus updated. Following this process, all the noncritical activities would be added to the schedule.

Where to place the noncritical activities can be achieved by aligning a newly added noncritical activity to existing activities in the schedule. An example is shown in Figure 5. The grey highlighted bar denotes the resource usage of the existing activities in the schedule. Two new activities with oblique lines are added to the schedule. To achieve the maximum reduction of RFC, the two activities should be aligned with the edge of existing activities. Thus, if the first activity may be located at P₁, the reduction of RRH is R₁ and if the second activity is added at the position P₂, the reduction is R₂ + R₃.

After added to the existing schedule, the two activities are merged to the existing schedule. The next noncritical activity is added based on the newly generated schedule where the maximum reduction of RFC could be achieved. This approach uses the greedy algorithm which makes the locally optimal choice at each stage with the hope of finding the global optimum. Therefore, each noncritical activity is added to the schedule one by one. The sequence of adding noncritical activities depends on the priority values of these noncritical activities. For all available noncritical activities, an activity with highest priority value will be chosen first to add the existing schedule to achieve the maximum reduction of RRH + MDR. However, this method cannot guarantee the final reduction of RRH + MDR attains maximum because the greedy algorithm only finds the locally optimum at each step without considering previous steps. This issue is discussed in the validation section. In the end, the total cost and project duration would be calculated in this module and returned to the EMO module.

3.4. The Local Search Module

The calculated results by the EMO module are further optimized by searching for the possible positions of the noncritical activities to ensure the maximum reduction of RRH + MRD. For each individual, the activity priority value and mode are determined. Then, apply the project scheduling module to calculate the total float and free float based on the generated schedule by using backward pass. Then to further minimize RRH + MRD, El-Rays’ method is applied to search the potential positions of the noncritical activities [25]. El-Rays used a GA technique to search the possible locations of noncritical activities. From the “right” to “left” in the schedule chart, the most right noncritical activity (i.e., latest finish time) is shifted first by the calculated value in Eq.(9) [25]. After shifting this activity, update the FF and TF of preceding activities. In this way, each noncritical activity is shifted. One difference from the original El-Rays’ method is that the shifting process should keep the resource feasible.

[picture] | (9)

= Actual shift-day for the activity i*.

Mi= Possible shift-day of the activity i*.

FFi* = Free Float of the activities i* when resource constraints are considered.

= Total Float of the activity i calculated by CPM without consideration of resource constraints.

Tmax= Specified maximum project duration.

= Fraction truncation.

P = priority value of activity i

N = the total number of activity.

Each individual of the population calculated by the EMO module would use the local search algorithm. If 30 individuals are finally generated by the EMO module, thus, the GA algorithm would run 30 times. Since the local search cannot guarantee finding the global optimum location, the results may be not necessarily better than results calculated by the EMO module. Therefore, the results calculated by the local search module will be compared with the results of the EMO module. The better results would be recorded as the final results.

3.5. Additional Considerations

RRH and RID are agreeable though each of them may have different applications. A strategy was proposed to reduce the cost incurred by both of the release/rehiring cost and idleness cost of resources. Here RIC is defined to measure the cost of resource idleness and RIC = unit cost for idle resource * RID. RHC has the same definition as RFC. In Figure 5, when the resource level is maintained at the level 2, the total cost = RIC* + RHC* (see (a) in Figure 5). RIC* is equal to the area indicated by the oblique lines. RHC* is equal to the length of the two arrow lines. The change of resource level may lead to different RIC and RHC.

In (b) of Figure 5, assume the resource level increased to the resource level 2 from the level 1, RHC is reduced while RIC is increased. To keep the total value of RHC and RIC minimum, the resource amount at the level 2 should be selected because the increasing of RIC below the level 2 is smaller than the decreasing of the RHC. This strategy may apply after the final calculation and allow users to select the resource level that reduce both of RHC and RIC.

Figure 5. Reduction of RHC and RIC

4. Model Validation

The model validation includes the analyzing runtime, estimating the expected RFC error due to the proposed chromosome representation, and testing the effectiveness of the model through computational experiment.

4.1. Time Complexity Analysis

The time complexity is adopted to evaluate the runtime of the model in terms of the number of the activities. The local search module is independent of the number of activity and thus the time complexity analysis is not conducted for this module.

Zitzler and Laumanns [33] analyzed the time complexity of the SPEA2 algorithm. The runtime is mainly composed of two parts. (a) Fitness assignment. This runtime is dominated by the density estimator (O(M²logM)), where M is the sum of the population and archive sizes. (b) Environment selection. The worst run-time complexity of the truncation operator is O(M³), however, the average runtime is lower than O(M²logM). For the project scheduling module, the time complexity is O() where n is the number of activities and K is the number of resources [36].

The runtime of the project leveling module is mainly consumed by calculating TF, adding and deducting the free activities, and calculating the RRH. The runtime of calculating the total float is about O() where TFi is the total l float of the activity i. Since TFi should be less than D denoting project duration). The maximum value of is nD. The runtime of the second part, adding and deducting the free activity is O() where di is the duration of activity i. Each location between ES and FS of an activity should be checked to make sure the resource constraint is not violated and checking each location requires a runtime of O(di) to add or deduct the resources. The third part, calculation of RFC, takes O(D) where D denotes the total project duration. Together, the total runtime of the resource leveling module is O().

The total runtime for the three modules was thus calculated by summation of the runtime of each module. For each individual in the EMO module, the runtime is the sum of the project scheduling and resource leveling modules, i.e., . There are a total of individuals where G denotes the generations and P denotes the population size for one generation. By adding the runtime of environmental selection, the total runtime of the worst case is . Thus, the runtime shown here is acceptable because it is polynomial times of the number of activities.

The testing of the total runtime of the model was done in a laptop with configuration of Windows 7 OS, 2.0 GHz CPU, 4G RAM. The EMO module is coded by C language while the other modules are coded in MATLAB. The total runtime of the three modules is about 30s for a project with ten activities.

4.2. RFC Error Analysis

The arrangement of noncritical activities in the resource leveling module uses greedy algorithm as indicated in Section 3.3. It is known that the sequence of adding noncritical activities to the schedule affects the value of RFC. However, even by checking all possible combinations of these noncritical activity sequence (the maximum number is n!), the greedy algorithm cannot still guarantee finding the maximum reduction of RFC. All the possible combinations of activity sequence (i.e., the priority values in the chromosome) would represent the search space of the EMO module. The EMO module searches the space to find the maximum reduction of RFC (i.e., minimum of RFC) in the space. However, the EMO module cannot find the global optimum of RFC. Two reasons may cause this result. One reason is that EMO can only find the near-optimum solutions as other evolutionary algorithms. The second reason is that the global optimum is not located in the search space of the EMO module and therefore the EMO module cannot find the global optimum of RFC even if searching the whole space. This section would address two issues related to the second reason: (a) when the global optimum is located in the search space; (b) if the global optimum is not located in the search space, what the expected error is.

To allow the EMO module to find the globally optimum of RFC, the greedy algorithm must add the noncritical activities in terms of the activity sequence which represents one point in the search space of EMO, to the schedule. The key problem here is whether to find an activity sequence (i.e., priority values of activities) in which the noncritical activities can be added to the globally optimum locations of the noncritical activities by using the greedy algorithm. Only if the globally optimum locations of the noncritical activities can be found by the greedy algorithm can the global optimum of RFC also be found by the EMO module. The globally optimum locations of the noncritical activities can be found by the greedy algorithm if satisfying one of the following two conditions: (1) no more than two noncritical activities are adjacent to each other, or at least one most outside edge of the adjacent noncritical activities is not adjacent to any of the critical activities (see (a) and (b) in Figure 6); or (2) if the globally optimum location of noncritical activities violates the condition (1), the global optimum is still located within the search space if there exists an activity sequence in which the noncritical activities could be added to the same locations as those optimum locations of noncritical activities are located (see (c) in Figure 6)

Figure 6. Illustration of conditions (1) and (2)

The conditions (1) and (2) are illustrated in Figure 6. The grey activities are noncritical and the activity 1 and the activity 2 are added to the schedule in order. According to the greedy algorithm, activity 1 should be added at position P₂ and activity 2 at position P₁ (see (a) and (b) in Figure 6). This sequence of adding the two noncritical activities could lead to the maximum reduction of RFC. For (b) in Figure 6, activities 1 and 2 are adjacent to each other but the right edge of the activity 2 is not adjacent to the critical activity. Thus, both (a) and (b) meet the condition (1). In (c) Figure 6, the condition (1) is violated. However by adding activity 1 and activity 2 in order, the global optimum reduction of RFC can still be achieved. Thus, (c) also meet the requirement of the condition (2). The arrangement of noncritical activities in (d) of Figure 6 shows the globally optimum locations of activities 1 and 2. The total reduction is R₁+R₂+R₃ (see (d)). However, if the greedy algorithm is applied, the locally optimum locations of the two activities are shown in (e) of Figure 6. The reduction is R₄+R₅, which is less than the value of R₁+R₂+R₃.

Condition (1) is briefly proved here. Assume the globally optimum locations of all noncritical activities are known, and then a noncritical activity with the smallest reduction of RFC can be first removed from the schedule while the optimum locations of the other noncritical activities are kept unchanged in the schedule chart, that is to say, these noncritical activities have larger RFC reduction in their original positions. All the noncritical activities can be removed from schedule in this way until only the critical activities are remained. Then if all the noncritical activities are added into the schedule (with only critical activities) in the reverse order by using greedy algorithm, the final locations of the noncritical activities would achieve the same reduction as the previous globally optimum locations of the noncritical activities.

When condition (1) is violated, the expected error is calculated to estimate the difference between the locally optimum locations found by EMO and the globally optimum locations. This can be shown in (c) and (d) of Figure 6. If there are two activities are adjacent, the reduction is R₄+R₅ if the greedy algorithm is applied while the global optimum reduction should be R₁+R₂+R₃. The difference (or, error) is about 1/3 of the globally maximum reduction if the values of R₁, R₂, R₃. R₄ and R₅ are assumed to be close. Similarly, if there are three activities adjacent (i.e., violating condition (1)), the error is ¼ of the globally maximum reduction of RFC. If there are i activities adjacent, the error is 1/(i+1). Assume the average reduction of RFC for each noncritical activity is t, and each noncritical activity has an equal possibility of meeting or violating the condition (1). In other words, from the perspective of the expectation, there are a₁ noncritical activities that are not adjacent to noncritical activities and critical activities in the schedule chart (i.e, just like (a) in Figure 6, meeting condition (1)), the error is 0%; also there are a₁ free activities that are only adjacent to one noncritical activity and critical activities (i.e., violating condition (1)) and the error is about (a₁/2) x (1/3) because two noncritical activities are adjacent to form only one whole block (as seen from (e) of Figure 6); similarly, there are a₁ free activities that are only adjacent to i noncritical activities and critical activities and the error is (ai/i) x [1/(i+1)]. The total noncritical activities would be a₁ x i. Since the assumption is made that each noncritical activity has an equal possibility of adjacent to different number of other noncritical activities, the expected error can be calculated by Eq. (10).

[picture] | (10)

If i is equal to 2 or 3, e would be about 8%, and if i becomes larger, e would become smaller. In addition, if the second condition (2) is considered, the value of e should be even smaller. Thus, it is concluded that the greed algorithm adopted in this research is reasonably accurate to ensure the locally optimum value of RFC calculated by the EMO module is close to the globally optimum reduction if it is assumes the EMO module has the ability to find the global optimum in the search space.

5. Conclusions

This research proposed a time-cost tradeoff model based on the SPEAII to optimize the project duration and resource cost by integrated consideration of the resource-constrained project scheduling and resource leveling. Resource rehiring/releasing cost was proposed to measure the resource fluctuation. The impact of resource fluctuation was thus converted to costs which could be added into the resource cost as an objective function.

The analysis of the time complexity of the model showed that the runtime was acceptable and had polynomial relationship with the number of activity. It took 30s to calculate the result for a ten-activity project. In additional, the model was evaluated in terms of the potential errors of resource fluctuation cost to justify the effectiveness of the chromosome representation.

However, due to the limitations of the baseline model, the developed model was not adequately validated. In addition, this model assumes the cost information such as unit cost of resource rehiring and releasing can be predetermined. In reality, it is sometime difficult to estimate all the cost information. Thus, the users have to run many times to compare the results if this cost information is uncertainty. Future work can be done by introducing the stochastic cost model to develop a more realistic model.

References

[1]   | Chen Y, Hu J, Mo P. “The Development of The Lifecycle Function Model By IDEF0 For Construction Projects,” in WiCOM 4th International Conference on Wireless Communications, Networking and Mobile Computing, IEEE, 1-4.
[2]   | Hu J, Flood I. “A multi-objective scheduling model for solving the resource-constrained project scheduling and resource leveling problems,” in Interntional Conference on Computing in Civil Engineering, Clearwater Beach, Florida, United States, 49-56.
[3]   | Zdamar L, Ulusoy G. “A survey on the resource-constrained project scheduling problem,” IIE TRANS, 27 (5), 574-86, 1995.
[4]   | Herroelen W, Leus R. “Project scheduling under uncertainty: Survey and research potentials,” EUR J OPER RES, 165 (2), 289-306, 2005.
[5]   | Burns SA, Liu L, Feng CW. “The LP/IP hybrid method for construction time-cost trade-off analysis,” Construction Management and Economics, 14 (3), 265-76, 1996.
[6]   | Deineko VG, Woeginger GJ. “Hardness of approximation of the discrete time-cost tradeoff problem,” OPER RES LETT, 29 (5), 207-10, 2001.
[7]   | Shen E, Patel M, Hu J. “Comparison of Energy and Visual Comfort Performance of Independent and Integrated Lighting and Daylight Controls Strategies,” in ACEEE Summer Study on Energy Efficiency in Industry, American Council for an Energy-Efficient Economy, New York, NY, USA.
[8]   | Pang X, Wetter M, Bhattacharya P, Haves P. “A framework for simulation-based real-time whole building performance assessment,” BUILD ENVIRON, 54 (0), 100-8, 2012.
[9]   | Hu J, Olbina S. “Radiance-based Model for Optimal Selection of Window Systems,” in ASCE 2012 International Conference on Computing in Civil Engineering, Clearwater Beach, FL, USA.
[10]   | Attia S, La Neuve L. Building Performance Simulation Tools: Selection Criteria and User Survey.; 2010.
[11]   | Olbina S, Hu J. “Daylighting and thermal performance of automated split-controlled blinds,” BUILD ENVIRON, 56 (0), 127, 2012.
[12]   | Hu J, Shen E, Gu Y. “Simulating Performance Risk for Lighting Retrofit Decisions,” Buildings, 5 (2), 650-67, 2015.
[13]   | Hu J, Olbina S. “Illuminance-based slat angle selection model for automated control of split blinds,” BUILD ENVIRON, 46 (3), 786-96, 2011.
[14]   | Georgy ME, Chang L, Zhang L. “Prediction of Engineering Performance: A Neurofuzzy Approach,” J CONSTR ENG M, 131 (5), 548-57, 2005.
[15]   | Chen P, Shahandashti SM. “Hybrid of genetic algorithm and simulated annealing for multiple project scheduling with multiple resource constraints,” AUTOMAT CONSTR, 18 (4), 434-43, 2009.
[16]   | Guo R, Guo W, Wang W. “Optimization of multi-project in limited resources on the basis of improved genetic algorithm,” in 2008 Pacific-Asia Workshop on Computational Intelligence and Industrial Application, Inst. of Elec. and Elec. Eng. Computer Society, Wuhan, China, 949-52.
[17]   | Hartmann S. “A competitive genetic algorithm for resource-constrained project scheduling,” NAV RES LOG, 45 (7), 733-50, 1998.
[18]   | Kolisch R. “Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation,” EUR J OPER RES, 90 (2), 320-33, 1996.
[19]   | Tsai DM, Chiu HN. “Two heuristics for scheduling multiple projects with resource constraints,” Construction Management & Economics, 14 (4), 325-40, 1996.
[20]   | Feng C, Liu L, Burns SA. “Using Genetic Algorithms to Solve Construction Time-Cost Trade-Off Problems,” J COMPUT CIVIL ENG, 11 (3), 184-9, 1997.
[21]   | Leu S, Chen A, Yang C. “A GA-based fuzzy optimal model for construction time-cost trade-off,” International Journal of Project Management, 19 (1), 47-58, 2001.
[22]   | Chen P, Weng H. “A two-phase GA model for resource-constrained project scheduling,” AUTOMAT CONSTR, 32 (1), 9-17, 2009.
[23]   | Wuliang P, Chengen W. “A multi-mode resource-constrained discrete time–cost tradeoff problem and its genetic algorithm based solution,” International Journal of Project Management, 201 (2), 409-18, 2009.
[24]   | Castro Lacouture D, Suer GA, Gonzalez Joaqui J, Yates JK. “Construction project scheduling with time, cost, and material restrictions using fuzzy mathematical models and critical path method,” J CONSTR ENG M, 135 (10), 1096-104, 2009.
[25]   | El-Rayes K, Jun DH. “Optimizing Resource Leveling in Construction Projects,” J CONSTR ENG M, 135 (11), 1172-80, 2009.
[26]   | Doulabi SHH, Seifi A, Shariat SY. “Efficient Hybrid Genetic Algorithm for Resource Leveling via Activity Splitting,” J CONSTR ENG M, 137 (2), 137-46, 2011.
[27]   | Hegazy T. “Optimization of resource allocation and leveling using genetic algorithms,” J CONSTR ENG M, 125, 167, 1999.
[28]   | Senouci AB, Eldin NN. “Use of genetic algorithms in resource scheduling of construction projects,” J CONSTR ENG M, 130, 869-77, 2004.
[29]   | Liao TW, Egbelu PJ, Sarker BR, Leu SS. “Metaheuristics for project and construction management - A state-of-the-art review,” AUTOMAT CONSTR, 20 (5), 491-505, 2011.
[30]   | Chan WT, Chua D, Kannan G. “Construction resource scheduling with genetic algorithms,” J CONSTR ENG M, 122, 125-32, 1996.
[31]   | Leu SS, Yang CH. “GA-based multicriteria optimal model for construction scheduling,” J CONSTR ENG M, 125, 420-7, 1999.
[32]   | Lucko G. “Integrating Efficient Resource Optimization and Linear Schedule Analysis with Singularity Functions,” J CONSTR ENG M, 1 (1), 164, 2010.
[33]   | Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength pareto evolutionary algorithm (Tech. Rep. No. 103)., Eurogen: Gloriastrasse; 2001.
[34]   | Coello C, Lamont GB, Van Veldhuizen DA. Evolutionary algorithms for solving multi-objective problems, Springer-Verlag New York Inc, New York, US, 2007.
[35]   | Hartmann S. “Project scheduling with multiple modes: A genetic algorithm,” ANN OPER RES, 102 (1), 111-35, 2001.
[36]   | Pinson E, Prins C, Rullier F. “Using tabu search for solving the resource-constrained project scheduling problem,” EURO-WG PMS, 4, 102-6, 1994.