Permutation-Based Particle Swarm Optimization for Resource-Constrained Project Scheduling

In the light of particle swarm optimization (PSO) which utilizes both local and global experiences during search process, a permutation-based scheme for the resource-constrained project scheduling problem (RCPSP) is presented. In order to handle the permutation-feasibility and precedence-constraint problems when updating the particle-represented sequence or solution for the RCPSP, a hybrid particle-updating mechanism incorporated with a partially mapped crossover of a genetic algorithm and a definition of an activity-move-range is developed. The particle-represented sequence should be transformed to a schedule (including start times and resource assignments for all activities) through a serial method and accordingly evaluated against the objective of minimizing project duration. Experimental analyses are presented to investigate the performances of the permutation-based PSO. The study aims at providing an alternative for solving the RCPSP in the construction field by utilizing the advantages of PSO.     

Comparing Schedule Generation Schemes in Resource-Constrained Project Scheduling Using Elitist Genetic Algorithm

An issue has arisen with regard to which of the schedule generation schemes will perform better for an arbitrary instance of the resource-constrained project scheduling problem (RCPSP), which is one of the most challenging areas in construction engineering and management. No general answer has been given to this issue due to the different mechanisms between the serial scheme and the parallel scheme. In an effort to address this issue, this paper compares the two schemes using a permutation-based Elitist genetic algorithm for the RCPSP. Computational experiments are presented with multiple standard problems. From the results of a paired difference experiment, the algorithm using the serial scheme provides better solutions than the one using the parallel scheme. The results also show that the algorithm with the parallel scheme takes longer to solve each problem than the one using the serial scheme.     

Particle Swarm Optimization for Preemptive Scheduling under Break and Resource-Constraints

This paper introduces a particle swarm optimization (PSO)-based methodology to implement preemptive scheduling under break and resource-constraints (PSBRC) for construction projects. The PSBRC under study allows the preemptive activities to be interrupted in off-working time and not to resume immediately in the next working period because all the limited resources are to be reallocated during a break. The potential solution to the PSBRC, i.e., a set of priorities deciding the order to start the activities or restart the interrupted activities, is represented by the multidimensional particle position. Hence PSO is applied to search for the optimal schedule for the PSBRC, in which a parallel scheme is adopted to transform the particle-represented priorities to a schedule. Computational analyses are presented to verify the effectiveness of the proposed methodology. This paper provides an attempt to make use of preemption and break for the resource-constrained construction project with the objective of minimizing project duration.     

Expanding Finance-Based Scheduling to Devise Overall-Optimized Project Schedules

Construction contractors often finance projects using bank credit lines that allow contractors to withdraw money up to certain credit limits. Finance-based scheduling provides schedules that ensure that the contractor’s indebtedness at any time during the construction stage does not exceed the credit limit. Generally, constricted credit limits tend to yield prolonged schedules. Provided that credit limits can be adequately relaxed, compressed schedules of compressed-duration activities can be attained. Devising a compressed schedule calls for the incorporation of time-cost trade-off (TCT) analysis to strike a balance between the decreased overhead costs and the increased direct costs of the activities. Since employing TCT analysis usually causes great fluctuations in the daily resource requirements by mixing compressed-duration activities of high resource demand with others of low resource demand, therefore, the need for resource management techniques becomes inevitable to ensure efficient utilization of resources. This note used genetic algorithms to expand finance-based scheduling to devise schedules for relaxed credit limits. A prototype system was developed and coded using VISUAL BASIC, then demonstrated using a five-activity example project. The prototype was validated by comparing the results with those obtained by using the integer programming. Expanding finance-based scheduling to handle the whole spectrum of credit limits helps devise overall-optimized schedules that consider cash, time, cost, and resources.     

Project Scheduling Using Fuzzy Set Concepts

Probabilistic methods are being used increasingly in construction engineering. However, when a parameter is expressed in linguistic rather than mathematical terms, classical probability theory fails to incorporate the information. The linguistic variables can be translated into mathematical measures using fuzzy set and system theory. A construction management problem, i.e., estimation of the duration of an activity, is solved using this theory. In order to implement the proposed technique, various membership functions need to be estimated using judgment or with the assistance of experts. The proposed technique is not sensitive to small variations in the membership values. This is a very desirable property. However, the method is sensitive to the choice of the fuzzy relations. The uncertainty in the fuzzy relations can be modeled along with other sources of uncertainty. The mean and variance of the parameters involved in the problem under consideration are estimated here using a new method. The method maximizes the product of the sum of the membership associations for a certain frequency of occurrence and the corresponding frequency of occurrence. One of the main advantages of the proposed technique is that it can be easily implemented in existing computer programs for project scheduling.     

Exact Algorithm for Solving Project Scheduling Problems under Multiple Resource Constraints

This paper presents a new algorithm, called the enumerative branch-and-cut procedure (EBAC), for minimizing the total project duration of a construction project under multiple resource constraints based on an enumeration tree. The EBAC generates new branches to the tree corresponding to “better” feasible alternatives. It starts with all of the feasible schedule alternatives as the trial schedule alternatives at any node. The trial schedule alternatives are then evaluated to determine whether they are “worse” than any existing partial schedules in the tree by using the presented cut rules, and a worse alternative will be eliminated from the enumeration tree. In other words, the tree will contain only better feasible schedules. The presented algorithm has been coded in the VB6.0 language on a personal computer. It has been tested with the 110 scheduling problems, which have been widely used for validating a variety of schedule algorithms over the last 20?years. The EBAC can obtain the shortest project durations for all of the 110 problems.     

Scheduling Resource-Constrained Projects with Ant Colony Optimization Artificial Agents

The paper presents a methodology to schedule resource-constrained construction projects by use of algorithms based on ant colony optimization (ACO); an artificial agent inspired by the collective behavior of natural ant colonies as they optimize their path from an origin (ant nest) to a destination (food source) by use of previously acquired knowledge. Further, to an application of the ACO artificial agent to a resource-unconstrained network topology, the method is applied to a resource-constrained network and utilized in examining the effects of resource availability constraints to critical path calculations and project completion time.     

Stochastic Time-Cost-Resource Utilization Optimization Using Nondominated Sorting Genetic Algorithm and Discrete Fuzzy Sets

In a construction project, the cost and duration of activities could change due to different uncertain variables such as weather, resource availability, etc. Resource leveling and allocation strategies also influence total time and costs of projects. In this paper, two concepts of time-cost trade-off and resource leveling and allocation have been embedded in a stochastic multiobjective optimization model which minimizes the total project time, cost, and resource moments. In the proposed time-cost-resource utilization optimization (TCRO) model, time and cost variables are considered to be fuzzy, to increase the flexibility for decision makers when using the model outputs. Application of fuzzy set theory in this study helps managers/planners to take these uncertainties into account and provide an optimal balance of time, cost, and resource utilization during the project execution. The fuzzy variables are discretized to represent different options for each activity. Nondominated sorting genetic algorithm (NSGA-II) has been used to solve the optimization problem. Results of the TCRO model for two different case studies of construction projects are presented in the paper. Total time and costs of the two case studies in the Pareto front solutions of the TCRO model cover more than 85% of the ranges of total time and costs of solutions of the biobjective time-cost optimization (TCO) model. The results show that adding the resource leveling capability to the previously developed TCO models provides more practical solutions in terms of resource allocation and utilization, which makes this research relevant to both industry practitioners and researchers.     

Finance-Based Scheduling: Tool to Maximize Project Profit Using Improved Genetic Algorithms

Contractor’s ability to procure cash to carry out construction operations represents a crucial factor to run profitable business. Bank overdrafts have always been the major source to finance construction projects. However, it is not uncommon that bankers set a limit on the credit allocated to an established overdraft. Bankers’ interest rates and consequently contractors’ financing costs are basically determined based on the allocated credit limits. Furthermore, project indirect costs are directly proportional to the project duration which is affected by the allocated credit limit. Thus, the credit limit affects project financing costs and indirect costs which in turn affect project profit. However, finance-based scheduling produces financially executable schedules at specified credit limits while maintaining the demand of time minimization. Thus, finance-based scheduling provides a tool to control the credit requirements. This control enables contractors to negotiate lower interest rates which reduce financing costs. Thus, finance-based scheduling enables contractors to reduce project indirect costs and financing costs. This paper utilizes genetic algorithm’s technique to devise finance-based schedules that maximize project profit through minimizing financing costs and indirect costs.     

Efficient Hybrid Genetic Algorithm for Resource Leveling via Activity Splitting

Resource leveling problem is an attractive field of research in project management. Traditionally, a basic assumption of this problem is that network activities could not be split. However, in real-world projects, some activities can be interrupted and resumed in different time intervals but activity splitting involves some cost. The main contribution of this paper lies in developing a practical algorithm for resource leveling in large-scale projects. A novel hybrid genetic algorithm is proposed to tackle multiple resource-leveling problems allowing activity splitting. The proposed genetic algorithm is equipped with a novel local search heuristic and a repair mechanism. To evaluate the performance of the algorithm, we have generated and solved a new set of network instances containing up to 5,000 activities with multiple resources. For small instances, we have extended and solved an existing mixed integer programming model to provide a basis for comparison. Computational results demonstrate that, for large networks, the proposed algorithm improves the leveling criterion at least by 76% over the early schedule solutions. A case study on a tunnel construction project has also been examined.     

Integrated Simulation System for Construction Operation and Project Scheduling

Simulation modeling is important in predicting the productivity of construction operations and the performance of project schedules. It would be desirable if operation and project models are vertically integrated in practice. However, existing discrete event simulation systems do not allow integrating operation and project models. This paper introduces an integrated simulation system named “Construction Operation and Project Scheduling” (COPS). COPS analyzes the productivity of construction operations as well as the performance of a project schedule individually and jointly. It creates operation models, maintains these models in its operation model library, conducts sensitivity analysis with different resource combinations, finds the optimal resource combination that satisfies the user’s requirements relative to hourly production and hourly cost of the operation, feeds this information into a project schedule, and executes stochastic simulation-based scheduling. A case study is presented to demonstrate this integrated simulation system.     

Use of Genetic Algorithms in Resource Scheduling of Construction Projects

This paper presents an augmented Lagrangian genetic algorithm model for resource scheduling. The algorithm considers scheduling characteristics that were ignored in prior research. Previous resource scheduling formulations have primarily focused on project duration minimization. Furthermore, resource leveling and resource-constrained scheduling have traditionally been solved independently. The model presented here considers all precedence relationships, multiple crew strategies, total project cost minimization, and time-cost trade-off. In the new formulation, resource leveling and resource-constrained scheduling are performed simultaneously. The model presented uses the quadratic penalty function to transform the resource-scheduling problem to an unconstrained one. The algorithm is general and can be applied to a broad class of optimization problems. An illustrative example is presented to demonstrate the performance of the proposed method.     

Challenges in Line-of-Balance Scheduling

The line-of-balance (LOB) method of scheduling is well suited to projects that are composed of activities of a linear and repetitive nature. The objective of this study is to set down the basic principles that can be used in the development of a computerized LOB scheduling system that overcomes the problems associated with existing systems and creates solutions to problems encountered in the implementation of repetitive-unit construction. The challenges associated with LOB scheduling include developing an algorithm that handles project acceleration efficiently and accurately, recognizing time and space dependencies, calculating LOB quantities, dealing with resource and milestone constraints, incorporating the occasional nonlinear and discrete activities, defining a radically new concept of criticalness, including the effect of the learning curve, developing an optimal strategy to reduce project duration by increasing the rate of production of selected activities, performing cost optimization, and improving the visual presentation of LOB diagrams.     

Project Time-Cost Trade-Off Optimization by Maximal Flow Theory

Time and cost are related on projects. Project managers are frequently required to make time-cost trade-offs. With the complexity of large projects and the schedule impact of time-cost modifications, decisions on time-cost optimization are usually done on a hit or miss basis. This technical note presents an innovative technique that can be used to automate and optimize the time-cost trade-off process. The technique is based on “maximum flow–minimal cut” theory. The method is an improvement over current practice.     

Applying Pareto Ranking and Niche Formation to Genetic Algorithm-Based Multiobjective Time–Cost Optimization

Time–cost optimization (TCO) is one of the greatest challenges in construction project planning and control, since the optimization of either time or cost, would usually be at the expense of the other. Although the TCO problem has been extensively examined, many research studies only focused on minimizing the total cost for an early completion. This does not necessarily convey any reward to the contractor. However, with the increasing popularity of alternative project delivery systems, clients and contractors are more concerned about the combined benefits and opportunities of early completion as well as cost savings. In this paper, a genetic algorithms (GAs)-driven multiobjective model for TCO is proposed. The model integrates the adaptive weight to balance the priority of each objective according to the performance of the previous “generation.” In addition, the model incorporates Pareto ranking as a selection criterion and the niche formation techniques to improve popularity diversity. Based on the proposed framework, a prototype system has been developed in Microsoft Project for testing with a medium-sized project. The results indicate that greater robustness can be attained by the introduction of adaptive weight approach, Pareto ranking, and niche formation to the GA-based multiobjective TCO model.     

Evaluation of the Resource-Constrained Critical Path Method Algorithms

This study evaluates the resource-constrained critical path method (RCPM), which the writers have recently proposed. RCPM establishes a critical path method (CPM)-like, resource-constrained schedule by resource-dependent activity relationships (or resource links) that the five-step RCPM technique identifies. With its CPM-like feature, RCPM provides the critical path and float data that are not available in traditional resource-constrained scheduling techniques. In addition, RCPM provides more flexibility to the schedule through identified alternative schedules, which allow certain activities to be executed beyond their late finish times without delaying the project completion. This paper evaluates the RCPM’s performance by comparing it with five related previous studies. A brief review of each study is also included in this paper. This comparison shows that RCPM performs well in identifying resource links and alternative schedules, compared to other methods. This study is of interest to academics because it highlights the advantages and disadvantages of different algorithms that have attempted to overcome present problems in traditional resource-constrained scheduling techniques.     

Construction Project Scheduling with Time, Cost, and Material Restrictions Using Fuzzy Mathematical Models and Critical Path Method

This article evaluates the viability of using fuzzy mathematical models for determining construction schedules and for evaluating the contingencies created by schedule compression and delays due to unforeseen material shortages. Networks were analyzed using three methods: manual critical path method scheduling calculations, Primavera Project Management software (P5), and mathematical models using the Optimization Programming Language software. Fuzzy mathematical models that allow the multiobjective optimization of project schedules considering constraints such as time, cost, and unexpected materials shortages were used to verify commonly used methodologies for finding the minimum completion time for projects. The research also used a heuristic procedure for material allocation and sensitivity analysis to test five cases of material shortage, which increase the cost of construction and delay the completion time of projects. From the results obtained during the research investigation, it was determined that it is not just whether there is a shortage of a material but rather the way materials are allocated to different activities that affect project durations. It is important to give higher priority to activities that have minimum float values, instead of merely allocating materials to activities that are immediately ready to start.     

Stochastic Network Model for Planning Scheduling

A stochastic network model consisting of dependent and independent random variables is developed for construction scheduling. The network model is based on Monte‐Carlo simulation. Data for each network activity consist of a time distribution for the activity under optimal conditions and a series of time distributions for various problems that may lengthen the activity completion time. Dependencies between network activities may be modelled; also, time dependencies for a network activity may be modelled. The implementation of the model is discussed.