Multi-mode resource-constrained discrete time–cost-resource optimization in project scheduling using non-dominated sorting genetic algorithm
Highlights
► We model MRCPSP, DTCTP, RL and RA problems simultaneously. ► Revised serial SGS is presented to generate schedules from given chromosomes. ► We examine resource leveling effects on project time and cost. ► Decreasing fluctuation in resource usage histogram will increase project cost. ► Scheduling models with resource leveling capability are more practical.
Introduction
Construction projects consist of complex activity network with precedence relationship among the activities, in which each activity can be performed in one of several execution modes. Each mode represents an alternative combination of resource requirements of the activity with related duration for accomplishment [1]. Selecting execution modes of activities in project scheduling mechanism depends on the project's objectives and constraints predicted by a high-level plan. In other words, project scheduling mechanism is an actual execution of the plan and tries to deliver its optimal performance into sequence of activities to be executed [2]. In today's competitive business environment, companies cannot survive without efficiently planning and scheduling. Critical path method (CPM) is widely used for project planning and scheduling in construction projects. It takes into account the time and determines critical activities to minimize project makespan, but the resource availability is not considered and an activity can start when all predecessor activities are completed. This is however impractical, because in a real project resource availability and allocation will affect the entire project scheduling [3]. To overcome CPM major limitations, several techniques and optimizations have been proposed in project management and scheduling literature and usually can be classified in four categories: resource constraint scheduling, time cost trade-off, resource leveling and resource allocation.
In resource constraint project scheduling problem (RCPSP), each activity must be scheduled considering resource constraint and precedence relationship between activities, in such a way that project makespan is minimized [4], [5]. It is a popular NP-hard optimization problem [6] and various searching methods including exact methods [7], [8], [9], heuristic [10], [11], [12], [13] and metaheuristic [1], [2], [3], [14], [15], [16] procedures have been proposed to solve this problem on the wide variety of assumptions. The generalized version of RCPSP is Multimode Resource-Constrained Project Scheduling Problem (MRCPSP) where each activity can be performed in one of several execution modes with related duration and resource requirements. Three types of resources are considered in this problem [17]: renewable, nonrenewable and doubly constrained. Renewable resource availability is limited per period of time (as machines or manpower), since nonrenewable resource availability is limited for an entire project (as a budget). Doubly constrained resource availability is limited both by period and for an entire project. MRCPSP belongs to the class of NP-hard problem and none of the exact algorithms are able to find optimal schedule for large and highly resource constrained project in reasonable time [18]. Therefore in practice heuristic and metaheuristic algorithms are needed to generate near optimal schedules. The work by Hartmann [1] and Alcaraz et al. [14] are examples of metaheuristic optimization based on genetic algorithm for solving MRCPSP with a makespan minimization as an objective. They used an activity list (AL) and a mode assignment list for chromosome representation. To overcome some drawbacks in [14], Lova et al. [19] proposed a new normalized fitness function in their hybrid genetic algorithm (MM-HGA) for solving MRCPSP. For more details and excellent review, we refer the reader to Kolisch & Hartmann [4], [5].
The schedule that is obtained from solving MRCPSP is more practical than solving its classic optimization problem. On the other hand, it is possible to expand MRCPSP to a more realistic and multi-objective optimization model for project management. When we include only one nonrenewable resource as an activity execution cost, we can solve the special case of MRCPSP known as a discrete time/cost trade off problem (DTCTP) in which both the effects of time–cost trade-off and resource scheduling will be taken into account. The DTCTP arises when duration of project activities is a discrete, non-increasing function of the amount of single nonrenewable resource committed to them. The DTCTP process is to select activities execution modes depending on three different objectives [20]. It could be used to minimize project cost while meeting a given deadline (deadline problem) or minimizing project duration without exceeding a given budget (budget problem). A third objective is to specify the entire time–cost profile over the feasible project durations (time–cost curve problem). It is a strongly NP-hard problem [21] and for complex networks only efficient heuristics and metaheuristics can obtain optimal/near optimal solutions. Different researchers such as Akkan [22], [23] have proposed heuristics in the area of discrete time–cost trade-off optimization. Vanhoucke et al. [20] extended this discrete time/cost trade-off problem type with the so-called time-switch constraints, which imposes specified starting times on the project activities and forces them to be active and inactive during specified time periods. In [24] Vanhoucke et al. proposed a new branch-and-bound algorithm which outperformed the previous one by Vanhoucke et al. [20]. In recent years researchers have developed their models to cope with more realistic settings. Time/switch constraints, work continuity constraints and net present value maximization elaborated as the extensions of discrete time/cost trade-off problem in [25] using the metaheuristic approach in order to provide near-optimal solutions. Wuliang & Chengen [16] presented a new multi-mode resource-constrained DTCTP model (MRC-DTCTP) by adding renewable resource constraints to the general DTCTP, where an improved genetic algorithm is developed to solve the problem. In their paper by predefining the resource price, the renewable resources have been related to the project costs, including direct cost and indirect cost. Uncertainties are considered in time–cost trade-off problems by Eshtehardian et al. [26]. The authors proposed an approach that embeds the fuzzy structure of the uncertainties in total direct cost into the model and used appropriate GA to develop a solution to the multi-objective fuzzy time cost model. Kalhor et al. [27] employed non-dominated archiving ant colony approach to solve a stochastic time–cost trade-off optimization problem and considering total project time and cost as two objectives. Fuzzy sets theory was used to answer for the uncertainties in time and cost of the project.
Despite the large amount of literature of the DTCTP, there are few researches [16], [28] that have considered the renewable resources impact in project scheduling. However, in real-life construction projects, many different types of renewable resources (including manpower, machines, equipments and etc.) are involved and resource management strategies like resource leveling would affect project's total time and cost. Resource leveling is a process that minimizes the variation of the resource usage over time, and thus, reduces excessive fluctuations of the resources usage during the project makespan, which could otherwise lead to a drop in productivity or an increase in production cost [29]. One of the earliest efforts to reduce resource level fluctuations is seen in Burgess and Killebrew [30]. In this study minimizing the variance of required resource is equivalent to minimizing the sum of the squares of this resource requirement on resource histogram. Neumann and Zimmermann [31] published a study in which heuristic procedures for solving RLP without and with explicit resource constraints have been introduced. Several different types of objectives including minimization of maximum resource costs per period, minimization of the deviations from a desired or uniform resource level and minimization of the variations in resource utilization curves over time have been discussed in this research. Hegazy [32] used a genetic algorithm for near-optimal solutions and considered resource leveling and allocation problem simultaneously. The method minimized the total project duration and appropriate moment(s) under resource constraints but did not include minimization of project cost. Schedule optimization with respect to time, cost, and resource constraints using a spreadsheet model was developed by Hegazy and Ersahin [33]. Senouci and Eldin [34] presented an augmented Lagrangian GA model for resource scheduling. In their model, resource leveling and resource-constrained scheduling are performed simultaneously and all precedence relationships, multiple crew strategies, total project cost minimization, and time–cost trade-off were considered. However the model did not consider resource allocation and different execution modes of activities. Roca et al. [2] extended resource leveling model as a multiobjective genetic algorithm based optimization that takes into account the minimization of the project makespan and the leveling of each resource usage over time. The method produced non-dominated solutions and did not seek project total cost minimization. Leu and Yang [35] developed a multicriteria optimization model for construction scheduling based on a genetic algorithm, which incorporated the time–cost trade-off, resource-constrained allocation, and the unlimited resource-leveling models. The model was implemented in two phases. In phase 1 non-dominated solutions were found with respect to time and cost functions under resource constraints and in phase 2 resource leveling was performed and the starting dates of activities were determined. Although several objectives have been considered by the model, they were not considered simultaneously in three-dimensional solution space. This fact prevented some good solutions to be selected in terms of resource leveling in phase 1. Two concepts of time–cost trade-off, resource leveling and allocation have been embedded in a stochastic multiobjective optimization model by Zahraie and Tavakolan [36] which minimizes the total project time, cost, and resource moments. In this research fuzzy set theory was applied to represent different options for each activity. Although it has been mentioned that the presented model is capable to deal with limited resources, the model did not consider the resource constrain scheduling problem during its process.
In this paper, the authors integrated the ideas from the aforementioned research to develop a multi-mode resource constrained discrete time–cost-resource optimization model (MRC-DTCRO) that considers MRCPSP, DTCTP and resource allocation and leveling problem simultaneously. Therefore the proposed model constitutes three objectives including minimum duration, minimum cost and minimum resources moment deviation on the project makespan. Finding non-dominated solutions employing the elitist non-dominated sorting genetic algorithm (NSGA-II) is the primary goal of the paper. The results of the MRC-DTCRO model for a simple example and a real construction project case study are also presented to demonstrate the model capabilities.
Section snippets
Proposed MRC-DTCRO model
The problem considered in this paper involves the scheduling of j = 1,…,J activities that are described in an activity-on-node network G = (V,E) where V and E represent the set of activities and finish-to-start precedence relationship (with lag 0) respectively. The activities are numbered from 0 to J + 1 in the project network, where activities 0 and J + 1 are “dummy” activities denoting the beginning and the end of the project. Precedence relation among some of the activities enforce that activity j
A genetic algorithm for MRC-DTCRO
The main goal of the study is to optimize time–cost-resource trade-off, which is formulated as a multi-objective optimization problem and search for non-dominated schedules that minimize the total duration, the total cost and the resource usage fluctuations simultaneously. In the multiobjective problems, often some of the criteria are in conflict with each other, i.e. an improvement in one objective can only be achieved by sacrificing another. Moreover, some criteria are not commensurable (i.e.
Model application and discussion of the results
To verify and determine the effectiveness of the proposed MRC-DTCRO model, two case studies have been chosen. The first case study is a simple project adapted from Hartmann [1] as a benchmark problem for model verification and the second case study is a simplified real construction project of warehouse which is adapted from Chen & Weng [3] to demonstrate model application. The proposed algorithm has been coded in MATLAB R2011b language. The experiment has been performed on a personal computer
Conclusion
The multi-mode resource constrained project scheduling problem (MRCPSP), the discrete time–cost trade-off problem (DTCTP), the resource allocation and resource leveling problem (RL) are well-established project scheduling problems. In this study, to solve these problems simultaneously, the general MRCPSP was extended to a new multi-mode resource-constrained discrete time–cost-resource optimization model (MRC-DTCRO) that selects the best combination of starting time and execution mode for each
References (40)
- et al.
Experimental investigation of heuristics for resource-constrained project scheduling: an update
European Journal of Operational Research
(2006) - et al.
Scheduling subject to resource constraints: classification and complexity
Discrete Applied Mathematics
(1983) - et al.
An algorithm for a general class of precedence and resource constrained scheduling problem
- et al.
A local constraint based analysis approach to project scheduling under general resource constraints
European Journal of Operational Research
(1994) - et al.
Hybrid genetic algorithm with adaptive abilities for resource-constrained multiple project scheduling
Computers in Industry
(2005) - et al.
Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm
European Journal of Operational Research
(1998) - et al.
An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes
International Journal of Production Economics
(2009) New computational results for the discrete time/cost trade-off problem with time-switch constraints
European Journal of Operational Research
(2005)- et al.
Stochastic time–cost optimization using non-dominated archiving ant colony approach
Journal of Automation in Construction
(2011) - et al.
Resource leveling for projects with schedule-dependent time windows
European Journal of Operational Research
(1999)
Serial and parallel resource-constrained project scheduling method revisited: theory and computation
European Journal of Operational Research
Project scheduling with multiple modes: a genetic algorithm
Annals of Operations Research
Solving an extended resource leveling problem with multiobjective evolutionary algorithms
World Academy of Science, Engineering and Technology
A two-phase GA model for resource-constrained project scheduling
Automation in Construction
Heuristic algorithms for solving the resource-constrained project scheduling problem: classification and computational analysis
Project scheduling with multiple modes: a comparison of exact algorithms
Networks
Resource-constrained project scheduling with time-resource trade-offs: the nonpreemptive case
Management Science
Heuristics for scheduling projects with resource restrictions and several resource-duration modes
International Journal of Production Research
Agent-based project scheduling
IIE Transactions
Local search for nonpreemptive multi-mode resource-constrained project scheduling
IIE Transactions
Cited by (165)
Time-cost-quality tradeoff considering resource-scheduling problems
2023, Ain Shams Engineering JournalAn integrated chance-constrained stochastic model for a preemptive multi-skilled multi-mode resource-constrained project scheduling problem: A case study of building a sports center
2023, Engineering Applications of Artificial IntelligenceExtensions of the resource-constrained project scheduling problem
2023, Automation in ConstructionA novel oppositional teaching learning strategy based on the golden ratio to solve the Time-Cost-Environmental impact Trade-Off optimization problems
2023, Expert Systems with ApplicationsAutomated generation of stacking plans for prefabricated panels transported by A-frame trailers
2023, Advanced Engineering Informatics