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.     

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.     

Cost Optimization in Projects with Repetitive Nonserial Activities

A practical model for scheduling and cost optimization of repetitive projects is proposed in this paper. The model objective is to minimize total construction cost comprising direct cost, indirect cost, interruption cost, as well as incentives and liquidated damages. The novelty of this model stems from four main aspects: (1) it is based on full integration of the critical path and the line of balance methodologies, thus considering crew synchronization and work continuity among nonserial activities; (2) it performs time-cost trade-off analysis considering a specified deadline and alternative construction methods with associated time, cost, and crew options; (3) it is developed as a spreadsheet template that is transparent and easy to use; and (4) it utilizes a nontraditional optimization technique, genetic algorithms, to determine the optimum combination of construction methods, number of crews, and interruptions for each repetitive activity. To automate the model, macroprograms were developed to integrate it with commercial scheduling software. Details of the model are presented, and an example project is used to demonstrate its benefits.     

聚合分期算法在露天矿中长期生产计划编制中的应用

露天矿中长期生产计划是在最终境界的基础上确定矿块的开采顺序,以获得最大的总净现值。采用整数规划的方法来求解露天矿生产计划编制问题（OPSP）时,由于实际矿山最终境界内矿块个数太多,构建整数规划模型需要大量的二进制变量,超出了现有求解器的能力,使得问题无法求解。针对这一问题提出矿块聚合和分期求解相结合的启发式算法：将空间上n3个相邻矿块聚合,然后通过启发式方法,分期次逐渐求解、逐步迭代、更新模型,以减少模型变量和约束。利用VC++编程并调用CPLEX求解器实现该算法,应用于某铜矿,实现了长期计划的自动编制。结果表明：该算法能够显著减少用整数规划法求解OPSP时的变量个数,成百倍地提高解算效率,在较短的解算时间之内得到较优的结果,解决了OPSP因变量规模太大而无法求解的问题,并且能够较好地应用于各种规模矿山的实际生产计划编制工作。     

Hybrid Time-Cost Optimization of Nonserial Repetitive Construction Projects

Time-cost trade-off analysis represents a challenging task because the activity duration and cost have uncertainty associated with them, which should be considered when performing schedule optimization. This study proposes a hybrid technique that combines genetic algorithms (GAs) with dynamic programming to solve construction projects time-cost trade-off problems under uncertainty. The technique is formulated to apply to project schedules with repetitive nonserial subprojects that are common in the construction industry such as multiunit housing projects and retail network development projects. A generalized mathematical model is derived to account for factors affecting cost and duration relationships at both the activity and project levels. First, a genetic algorithm is utilized to find optimum and near optimum solutions from the complicated hyperplane formed by the coding system. Then, a dynamic programming procedure is utilized to search the vicinity of each of the near optima found by the GA, and converges on the global optima. The entire optimization process is conducted using a custom developed computer code. The validation and implementation of the proposed techniques is done over three axes. Mathematical correctness is validated through function optimization of test functions with known optima. Applicability to scheduling problems is validated through optimization of a 14 activity miniproject found in the literature for results comparison. Finally implementation to a case study is done over a gas station development program to produce optimum schedules and corresponding trade-off curves. Results show that genetic algorithms can be integrated with dynamic programming techniques to provide an effective means of solving for optimal project schedules in an enhanced realistic approach.     

Time-Profit Trade-Off Analysis for Construction Projects

This paper presents a multiobjective optimization model that provides new and unique capabilities including generating and evaluating optimal/near-optimal construction resource utilization and scheduling plans that simultaneously minimize the time and maximize the profit of construction projects. The computations in the present model are organized in three major modules: (1) a scheduling module that develops practical schedules for construction projects; (2) a profit module that computes the project profit; and (3) a multiobjective module that searches for and identifies optimal/near optimal trade-offs between project time and profit. A large-scale construction project is analyzed to illustrate the use of the model and to demonstrate its capabilities in generating and visualizing optimal trade-offs between construction time and profit.     

Optimum Planning of Highway Construction under A + B Bidding Method

In recent years, many departments of transportation in the United States have started to apply the A + B bidding method in highway projects in order to reduce construction time and minimize its associated traffic congestion and adverse impact on local economies. The application of this method places an increased pressure on contractors to minimize both the time and cost of highway construction. This paper presents a practical model for optimizing resource utilization in highway projects that utilize the A + B bidding method. The model is designed to minimize the total combined bid by identifying the optimum crew formation and the optimum level of crew work continuity for each activity in the project. The model is developed using a dynamic programming formulation and is incorporated in a Windows application that provides a user-friendly interface to facilitate the optimization analysis. An application example of a highway project is analyzed to illustrate the use of the model and to demonstrate its capabilities.     

Shuffled Complex Evolution Algorithms in Infrastructure Works Programming

Practical optimization of infrastructure preservation works programming has always posed a computational challenge due to the complexity and scale of the problem. Critical to the process is formulations in which the identity of individual projects is preserved. This requirement leads to exponential growth of solution space, often resulting in an unmanageable process using traditional analytical optimization techniques. In this paper, we propose an evolutionary-based multiyear optimization procedure for solving network level infrastructure works programming problems using a relatively new concept known as the shuffled complex evolution algorithm. A case study problem is analyzed to illustrate the robustness of the technique. The findings show convergence characteristics of the solution and demonstrate that the algorithm is very efficient and consistent in simultaneous consideration of the trade-off among various infrastructure preservation strategies. It is concluded that the robust search capability of the shuffled complex evolution technique is well suited for solving the combinatorial problems in network level infrastructure preservation works programming.     

Optimization technology of scheduling for hot-rolling mill

To establish the rolling plan of cold-rolling flattening set is very complicated,it is restrained by several constraints of rolling schedule.Operator’s subjective and other human factors also affect the rationality of plan arrangement seriously.Its result causes many abuses such as overusing transition strip,high-frequent roller switching,no-fully utilization of rollers,low arrangement rate of the plan.Therefore,we have initially developed a practical optimization model of rolling plan and schedule,which could be established and optimized by computer automatically,and a dynamic alignment module which have friendly UI according to the experience of operators.They have greatly enhanced the system usability.This system takes full advantage of relationship between the roller roughness and the rolling weight,reasonably arranges rolling based on different roughness demand,effectively enhances the use factor of roller and the smooth quality of steel string coil. A practical and effective scheduling optimization algorithm and rolling scheduling optimization applications system was developed based on the study of mixed hot rolling scheduling optimization model of carbon steel,stainless steel,stainless steel and carbon steel cross-rolling.The online application indicates that the model and algorithm is designed reasonable,practical and effective.This model system can significantly improve the scheduling efficiency and quality and it’s also very positive in reducing heating energy consumption,enhancing the volume of units rolling plan,and optimizing the production of hot-rolled unit organization and planning and scheduling.     

Constraint Programming Approach to Precast Production Scheduling

Current scheduling practices in precast plants are fairly basic and depend greatly on experience. This may lead to inefficient resource utilization, over-inventory, and/or missing delivery dates. Computer assisted scheduling may therefore be useful in producing better production schedules. This paper shows how constraint programming (CP) can be applied in production scheduling for precast plants. The paper describes a constrained precast scheduling model that incorporates the key constraints and objectives considered by production schedulers. A capacity-based backward-scheduling earliest due date rule and a CP approach are developed to solve the model. The CP approach is computationally efficient, even though it incorporates many problem-derived constraints. The efficiency of the CP approach lies in the fact that the representation (model) is separated from the algorithm (solver). Strategies to improve the performance of the CP approach are identified, and the CP approach is compared against commonly used heuristic rules on an example problem.     

Simplified Spreadsheet Solutions.?II: Overall Schedule Optimization

Overall schedule optimization, considering time, cost, and resource constraints is a difficult task due to the inherent complexity of projects, the difficulties associated with modeling all aspects combined, and the inability of traditional optimization tools to solve this large-size problem. In this paper, a practical approach is presented for the modeling and optimization of overall construction schedules. To simplify modeling, a spreadsheet-based model is developed to be easily usable by practitioners. The spreadsheet model integrates critical-path network scheduling with time-cost trade-off analysis, resource allocation, resource leveling, and cash flow management. The model uses the total project cost as the objective function to be minimized. To facilitate this large-size optimization, a nontraditional optimization technique, genetic algorithms, is used to locate the globally optimal solution, considering all aspects simultaneously. Details of the proposed model are described, and a hypothetical case study was used to experiment with it. Integration of the model with a simple information system is described to automate the development of optimal construction schedules.     

Object-Oriented Model for Repetitive Construction Scheduling

This paper presents the development of an object-oriented model for scheduling of repetitive construction projects such as high-rise buildings, housing projects, highways, pipeline networks, bridges, tunnels, railways, airport runways, and water and sewer mains. The paper provides an overview of the analysis, design, and implementation stages of the developed object-oriented model. These stages are designed to provide an effective model for scheduling repetitive construction projects and to satisfy practical scheduling requirements. The model incorporates newly developed procedures for resource-driven scheduling of repetitive activities, optimization of repetitive construction scheduling, and integration of repetitive and nonrepetitive scheduling techniques. The model is named LSCHEDULER and is implemented as a windows application that supports user-friendly interface including menus, dialogue boxes, and windows. LSCHEDULER can be applied to perform regular scheduling as well as optimized scheduling. In optimized scheduling, the model can assist in identifying an optimum crew utilization option for each repetitive activity in the project that provides a minimum duration or cost for the scheduled repetitive construction project.     

Multireservoir Systems Optimization Using Genetic Algorithms: Case Study

A genetic algorithm approach is presented for the optimization of multireservoir systems. The approach is demonstrated through application to a reservoir system in Indonesia by considering the existing development situation in the basin and two future water resource development scenarios. A generic genetic algorithm model for the optimization of reservoir systems has been developed that is easily transportable to any reservoir system. This generality is a distinct practical advantage of the genetic algorithm approach. A comparison of the genetic algorithm results with those produced by discrete differential dynamic programming is also presented. For each case considered in this study, the genetic algorithm results are very close to the optimum, and the technique appears to be robust. Contrary to methods based on dynamic programming, discretization of state variables is not required. Further, there is no requirement for trial state trajectories to initiate the search using a genetic algorithm. Model sensitivity and generalizations that can be drawn from this and earlier work by Wardlaw and Sharif are also considered.     

C-RAN回传网络中下行资源调度策略

随着移动互联网技术的快速发展、无线终端设备与移动应用流量需求与日俱增,移动用户对无线通信网络的服务质量(quality of service, QoS)要求越来越高、回传网络的压力也越来越大. 新出现的云无线接入网(cloud radio access network, C-RAN)能够有效提升网络容量、提高用户服务质量,同时采用无源光网络(passive optical network, PON)作为其回传网络(backhaul),能够为其提供大带宽、高可靠、低时延的回传支撑. 在移动应用需求不断变化和回传网络资源有限的条件下,高效的资源调度策略至关重要,其能够有效的提升回传网络资源利用率、降低传输等待时延. 为节约回传网络波长资源、提高波长负载均衡性和资源利用率,提出一种下行资源调度策略. 根据高热点区域无线用户实时网络需求,综合考虑回传网络波长使用数量、负载均衡性和实时业务分配均匀度等优化目标,采用自适应权重并行遗传算法完成其优化过程,从而实现波长资源动态分配,提升网络资源利用率. 仿真结果表明,提出的下行资源调度策略能有效提高网络负载均衡性和网络资源利用率,并降低实时业务等待传输时间.      

Work Continuity Constraints in Project Scheduling

Repetitive projects involve the repetition of activities along the stages of the project. Since the resources required to perform these activities move from one stage to the other, a main objective of scheduling these projects is to maintain the continuity of work of these resources so as to minimize the idle time of resources. This requirement, often referred to as work continuity constraints, involves a tradeoff between total project duration and the resource idle time. The contribution of this paper is threefold. First, we provide an extensive literature summary of the topic under study. Although most research papers deal with the scheduling of construction projects, we show that this can be extended to many other environments. Second, we propose an exact search procedure for scheduling repetitive projects with work continuity constraints. This algorithm iteratively shifts repeating activities further in time in order to decrease the resource idle time. We have embedded this recursive search procedure in a horizon-varying algorithm in order to detect the complete tradeoff profile between resource idle time and project duration. The procedure has been coded in Visual C++ and has been validated on a randomly generated problem set. Finally, we illustrate the concepts on three examples. First, the use of our new algorithm is illustrated on a small fictive problem example from literature. In a second example, we show that work continuity constraints involve a tradeoff between total project duration and the resource idle time. A last example describes the scheduling of a well-known real-life project that aims at the construction of a tunnel at the Westerschelde in The Netherlands.     

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.     

Irrigation Scheduling with Genetic Algorithms

A typical irrigation scheduling problem is one of preparing a schedule to service a group of outlets that may be serviced simultaneously. This problem has an analogy with the classical multimachine earliness/tardiness scheduling problem in operations research (OR). In previously published work, integer programming was used to solve irrigation scheduling problems; however, such scheduling problems belong to a class of combinatorial optimization problems known to be computationally demanding. This is widely reported in OR literature. Hence integer programs (IPs) can be used only to solve relatively small problems typically in a research environment where considerable computational resources and time can be allocated to solve a single schedule. For practical applications, metaheuristics such as genetic algorithms, simulated annealing, or tabu search methods need to be used. However, these need to be formulated carefully and tested thoroughly. The current research explores the potential of genetic algorithms to solve the simultaneous irrigation scheduling problem. For this purpose, two models are presented: the stream tube model and the time block model. These are formulated as genetic algorithms, which are then tested extensively, and the solution quality is compared with solutions from an IP. The suitability of these models for the simultaneous irrigation scheduling problem is reported.     

Optimized Scheduling of Linear Projects

This paper presents a model, designed to optimize scheduling of linear projects. The model employs a two-state-variable, N-stage, dynamic programming formulation, coupled with a set of heuristic rules. The model is resource-driven, and incorporates both repetitive and nonrepetitive activities in the optimization process to generate practical and near-optimal schedules. The model optimizes either project construction duration, total cost, or their combined impact for what is known as cost-plus-time bidding, also referred to as A+B bidding. The model has a number of interesting and practical features. It supports multiple crews to work simultaneously on any activity, while accounting for: (1) multiple successors and predecessors with specified lead and lag times; (2) the impact of transverse obstructions, such as rivers and creeks, on crew assignments and associated time and cost; (3) the effect of inclement weather and learning curve on crew productivity; and (4) variations in quantities of work in repetitive activities from one unit to another. The model is implemented in a prototype software that operates in Windows? environment. It is developed utilizing object-oriented programming, and provides for automated data entry. Several graphical and tabular output reports can be generated. An example project, drawn from the literature, is analyzed to demonstrate the features of the developed model.     

钢坯热轧加热炉区生产调度模型与算法

钢坯热轧加热炉区生产调度属于组合优化中的NP-complete问题.本文根据加热炉区生产特点建立了分别以生产能耗最小化和加热质量最优化为主次目标的钢坯加热炉区调度数学模型,将其归结为布尔可满足性问题,构造了采用二进制编码方式的遗传禁忌搜索算法进行求解.基于实际生产数据的模拟优化结果表明,该模型和求解方法充分满足了现场加热炉区生产调度的需求,在满足生产工艺约束的前提下,缩短了生产时间,提高了钢坯入炉温度和加热质量,与传统人工调度方法的结果相比具有更好的节能、高产效果.      

Optimization Research: Enhancing the Robustness of Large-Scale Multiobjective Optimization in Construction

Many construction planning problems require optimizing multiple and conflicting project objectives such as minimizing construction time and cost while maximizing safety, quality, and sustainability. To enable the optimization of these construction problems, a number of research studies focused on developing multiobjective optimization algorithms (MOAs). The robustness of these algorithms needs further research to ensure an efficient and effective optimization of large-scale real-life construction problems. This paper presents a review of current research efforts in the field of construction multiobjective optimization and two case studies that illustrate methods for enhancing the robustness of MOAs. The first case study utilizes a multiobjective genetic algorithm (MOGA) and an analytical optimization algorithm to optimize the planning of postdisaster temporary housing projects. The second case study utilizes a MOGA and parallel computing to optimize the planning of construction resource utilization in large-scale infrastructure projects. The paper also presents practical recommendations based on the main findings of the analyzed case studies to enhance the robustness of multiobjective optimization in construction engineering and management.