Evaluation of a Genetic Algorithm for the Irrigation Scheduling Problem

A typical irrigation scheduling problem is one of preparing a schedule to service a group of outlets which may be serviced simultaneously. This problem has an analogy with the classical earliness/tardiness problem in operations research. In previously published work an integer program was used to solve this problem, however such scheduling problems belong to a class of combinatorial problems known to be computationally demanding (N-P hard). This is widely reported in operations research. Hence integer programs can only be used to solve relatively small problems usually 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 as reported in the literature, these need to be formulated carefully and tested thoroughly. This paper demonstrates the importance of robust testing of one such genetic algorithm formulated to solve the irrigation scheduling problem with simultaneous outlets serviced against an integer program formulated to solve the same problem.     

Irrigation Scheduling. I: Integer Programming Approach

This paper shows how a sequential irrigation schedule for a tertiary unit can be interpreted as a single machine scheduling problem with earliness, tardiness, and a common deadline. An integer program solution is presented for this irrigation scheduling problem. Two different models are presented to reflect different management options at the tertiary level. The first model allows jobs to be scheduled noncontiguously. In the second model only contiguous jobs are allowed. The second model has three submodels reflecting the various ways in which contiguous jobs can be scheduled over a fixed interval. Earlier work in determining unit costs of earliness/tardiness is reviewed and an alternative improved method is suggested. The models presented in this paper are applied to a tertiary unit with 16 users, both as a single interval and multi-interval irrigation scheduling problem. An alternative integer program is also presented which although computationally more efficient can only be used for single period scheduling problems. The models developed in this paper can be used to solve small scheduling problems and also to calibrate the heuristics as presented in the companion paper.     

Irrigation Scheduling. II: Heuristics Approach

A sequential irrigation schedule that honors user demands of duration and minimizes earliness and tardiness is interpreted as a single-machine schedule with earliness and tardiness costs and a common deadline (or fixed interval). A heuristic solution is presented for this irrigation scheduling problem. Four models are presented to reflect the different methods in which an irrigation system at the tertiary unit level may be operated, the first model permits jobs to be noncontiguous, i.e., idle time between jobs is permitted, whereas the others permit contiguous jobs only. The heuristic is tested extensively and the solution quality is compared with either an optimum solution from an integer program or the best available solution obtained from an integer program within allocated computation time. The heuristic is computationally efficient for all models presented, however for schedules with noncontiguous jobs, or where idle time is inserted before and after a contiguous set of jobs, solution quality deteriorates. The work brings the science of single scheduling from operations research into irrigation scheduling and suggests areas for further development.     

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

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

Coupled Reservoir Operation-Irrigation Scheduling by Dynamic Programming

This paper develops a forward dynamic programming (FDP) model to solve the problem of reservoir operation and irrigation scheduling. The typical scenario for application of the model is composed of a system of two reservoirs in parallel supplying water to as many as three irrigation districts. Two models are coupled. The interseasonal model defines seasonal deliveries from the reservoir system. The intraseasonal model uses area and water allocations generated from the interseasonal model to produce an irrigation scheduling for the individual farms in one of the irrigation districts in the reservoir system. Crop evapotranspiration, reservoir evaporation, and inflows are forecasted. Upon availability of the current values, the forecast is updated and the model runs to generate a more precise irrigation schedule. This feature permits the application of the model for real-time operation of the irrigation district. At the end of the season, the intraseasonal model is updated. The FDP model is applied to a real watershed with a 2 year planning horizon for the interseasonal and 6 months for the intraseasonal model.     

炼钢连铸调度的启发式和线性规划两步优化算法

有效的连铸调度系统对钢铁企业提高产品质量和生产率具有重要意义。本文针对某大型钢铁企业炼钢连铸生产调度问题，提出了一系列启发式算法，分别用于解决作业排序、设备分配及时间安排问题以获得高质量的粗调度，提出了总流程时间的下界值计算方法用于评价调度结果。开发的调度软件可在生成粗调度之后自动导出其线性规划数学模型并求解。最后通过对实际生产数据的仿真分析，说明了算法的有效性和调度软件的实用性。     

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.     

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.     

Optimum Design and Management of Pressurized Branched Irrigation Networks

The scarcity of water resources is the driving force behind modernizing irrigation systems in order to guarantee equal rights to all beneficiaries and to save water. Traditional distribution systems have the common shortcoming that water must be distributed through some rotational criteria. This type of distribution is necessary to spread the benefits of scarce resources. Irrigation systems based on on-demand delivery scheduling offer flexibility to farmers and greater potential profit than other types of irrigation schedules. However, in this type of irrigation system, the network design has to be adequate for delivering the demand during the peak period whilst satisfying minimum pressure constraints along with minimum and maximum velocity constraints at the farm delivery points (hydrants) and in the pipes, respectively. In this paper, optimum design and management of pressurized irrigation systems are considered to be based on rotation and on-demand delivery scheduling using a genetic algorithm. Comparison is made between the two scheduling techniques by application to two real irrigation systems. Performance criteria are formulated for the optimum design of a new irrigation system and better management of an existing irrigation system. The design and management problems are highly constrained optimization problems. Special operators are developed for handling the large number of constraints in the representation and fitness evaluation stages of the genetic algorithm. The performance of the developed genetic algorithm is assessed in comparison to traditional optimization techniques. It is shown that the methodology developed performs better than the linear programming method and that solutions generated by the modified genetic algorithm show an improvement in capital cost. The method is also shown to perform better in satisfying the constraints. Comparison between on-demand and rotation delivery scheduling shows that a greater than 50% saving can be achieved in total cost at the cost of reducing flexibility in the irrigation time. Finally, it is shown that minimizing standard deviation of flow in pipes does not result in the best distribution, and therefore minimum cost, neither for systems with uniform flows or those with large variations in discharge at hydrants.     

Scheduling∕Cost Optimization and Neural Dynamics Model for Construction

A general mathematical formulation is presented for the scheduling of construction projects and is applied to the problem of highway construction scheduling. Repetitive and nonrepetitive tasks, work continuity constraints, multiple-crew strategies, and the effects of varying job conditions on the performance of a crew can be modeled. An optimization formulation is presented for the construction project scheduling problem, with the goal of minimizing the direct construction cost. The nonlinear optimization is then solved by the neural dynamics model developed recently by Adeli and Park. For any given construction duration, the model yields the optimum construction schedule for minimum construction cost automatically. By varying the construction duration, one can solve the cost-duration trade-off problem and obtain the global optimum schedule and the corresponding minimum construction cost. The new construction scheduling model provides the capabilities of both the critical path method (CPM) and linear scheduling method (LSM) approaches. In addition, it provides features desirable for repetitive projects, such as highway construction, and allows schedulers greater flexibility. It is particularly suitable for studying the effects of change order on the construction cost. This research provides the mathematical foundation for development of a new generation of more general, flexible, and accurate construction scheduling systems.     

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.     

Transit Route Network Design Using Parallel Genetic Algorithm

A transit route network design (TRND) problem for urban bus operation involves the determination of a set of transit routes and the associated frequencies that achieve the desired objective. This can be formulated as an optimization problem of minimizing the total system cost, which is the sum of the operating cost and the generalized travel cost. A review of previous approaches to solve this problem reveals the deficiency of conventional optimization techniques and the suitability of genetic algorithm (GA) based models to handle such combinatorial optimization problems. Since GAs are computationally intensive optimization techniques, their application to large and complex problems is limited. The computational performance of a GA model can be improved by exploiting its inherent parallel nature. Accordingly, two parallel genetic algorithm (PGA) models are proposed in this study. The first is a global parallel virtual machine (PVM) parallel GA model where the fitness evaluation is done concurrently in a parallel processing environment using PVM libraries. The second is a global message passing interface (MPI) parallel GA model where an MPI environment substitutes for the PVM libraries. An existing GA model for TRND for a large city is used as a case study. These models are tested for computation time, speedup, and efficiency. From the study, it is observed that the global PVM model performed better than the other model.     

Feasibility Study of 4D CAD in Commercial Construction

This paper concludes that 4D models are a useful alternative to project scheduling tools like CPM networks and bar charts. They enable more people to understand a schedule quickly and identify potential problems. By developing a 4D model for a commercial construction project, we were able to detect the incompleteness of the original schedule, find inconsistencies in the level of detail among the schedule activities, and discover an impossible schedule sequence. We were also able to anticipate potential time-space conflicts and accessibility problems. The results of the case study show that 4D models are effective in evaluating the executability of a construction schedule. The case study also highlighted the need for improvements to 4D tools. 4D tools should include bar charts, component lists, and annotation tools in their graphical user interface. Automating schedule data preparation and 4D model generation in the design stages of a project can expedite 4D model development and use. Users need to be able to generate 4D models at multiple levels of detail and generate and evaluate alternative scenarios rapidly.     

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.     

Optimal Sampling Design Methodologies for Water Distribution Model Calibration

Sampling design (SD) for water distribution systems (WDS) is an important issue, previously addressed by various researchers and practitioners. Generally, SD has one of several purposes. The aim of the methodologies developed and presented here is to find the optimal set of network locations for pressure loggers, which will be used to collect data for the calibration of a WDS model. First, existing SD approaches for WDS are reviewed. Then SD is formulated as a multiobjective optimization problem. Two SD models are developed to solve this problem, both using genetic algorithms (GA) as search engines. The first model is based on a single-objective GA (SOGA) approach in which two objectives are combined into one using appropriate weights. The second model uses a multiobjective GA (MOGA) approach based on Pareto ranking. Both SD models are applied to two case studies (literature and real-life problems). The results show several advantages and one disadvantage of the MOGA model when compared to SOGA. A comparison of the MOGA SD model solution to the results of several published SD models shows that the Pareto optimal front obtained using MOGA acts as an envelope to the Pareto fronts obtained using previously published SD models.     

Efficient Repetitive Scheduling for High-Rise Construction

A new scheduling and cost optimization model for high-rise construction is presented in this paper. The model has been formulated with a unique representation of the activities that form the building’s structural core, which need to be dealt with carefully to avoid scheduling errors. In addition, the model has been formulated incorporating: (1) the logical relationships within each floor and among floors of varying sizes; (2) work continuity and crew synchronization; (3) optional estimates and seasonal productivity factors; (4) prespecified deadline, work interruptions, and resource constraints; and (5) a genetic algorithms-based cost optimization that determines the combination of construction methods, number of crews, and work interruptions that meet schedule constraints. A computer prototype was then developed to demonstrate the model’s usefulness on a case study high-rise project. The model is useful to both researchers and practitioners as it better suits the environment of high-rise construction, avoids scheduling errors, optimizes cost, and provides a legible presentation of resource assignments and progress data.     

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.     

Irrigation Scheduling with Travel Times

In preparing water allocation schedules for fields in a lateral unit, the time required for water to travel from one point on a lateral to another can be significant and is dependent on the sequence in which users abstract water. This paper illustrates the problem of ignoring travel time and/or considering travel time to be sequence independent. For two users, each requesting water for a duration of 4 h, by assuming travel time to be sequence independent, one user receives water for 5 h, a 25% increase, and the other receives water for only 3 h, a 25% decrease. This paper presents a formulation of the irrigation scheduling problem for sequential users with sequent dependent travel time. The formulation is implemented as an integer program and applied to part of a lateral unit on the Juan Distributary, Haryana, India. Two models are presented, the first of which allows for noncontiguous jobs, i.e., idle time is permitted between jobs. The second model does not permit noncontiguous jobs.     

OCCASION: New Planning Tool for Optimal Climate Change Adaption Strategies in Irrigation

To sustain productive irrigated agriculture with limited water resources requires a high water use efficiency. This can be achieved by the precise scheduling of deficit irrigation systems taking into account the crops’ response to water stress at different stages of plant growth. Particularly in the light of climate change with rising population numbers and increasing water scarcity, an optimal solution for this task is of paramount importance. We solve the corresponding complex multidimensional and nonlinear optimization problem, i.e., finding the ideal schedule for maximum crop yield with a given water volume by a well tailored approach which offers straightforward application facilities. A global optimization technique allows, together with physically based modeling, for the risk assessment in yield reduction considering different sources of uncertainty (e.g., climate, soil conditions, and management). A new stochastic framework for decision support is developed which aims at optimal climate change adaption strategies in irrigation. It consists of: (1) a weather generator for simulating regional impacts of climate change; (2) a tailor-made evolutionary optimization algorithm for optimal irrigation scheduling with limited water supply; and (3) mechanistic models for rigorously simulating water transport and crop growth. The result, namely, stochastic crop-water production functions, allows to assess the impact of climate variability on potential yield and thus provides a valuable tool for estimating minimum water demands for irrigation in water resources planning and management, assisting furthermore in generating maps of yield uncertainty for specific crops and specific agricultural areas. The tool is successfully applied at an experimental site in southern France. The impacts of predicted climate variability on maize are discussed.     

Improvement Algorithm for Limited Space Scheduling

Selecting construction methods, scheduling activities, and planning the use of site space are key to constructing a project efficiently. Site layout and activity scheduling have been tackled as independent problems. Their interdependence is often ignored at the planning stage and may be dealt with—if at all—when construction is underway. Problems that may have had easy solutions if dealt with earlier, may then be expensive to remedy. This paper addresses the combined problem termed “space scheduling” and presents an algorithmic time-space trade-off model for adjusting activity durations and start dates to decrease the need for space over congested time periods. The model characterizes resource space requirements over time and establishes a time-space relationship for each activity in the schedule, based on alternative resource levels. An example illustrates the presented algorithm that generates a feasible space schedule.