Resource-Constrained Scheduling
What is it and why do we care?
Construction management is all about managing resources (labor, material, equipment, cost), for the purpose of achieving time, budget and quality targets. In a perfect world, the required resources are there for a project to use. But, in reality, resources are limited and not available when needed.
Resource-Constrained Scheduling Problems (RCSP) refer to a class of scheduling problems the activities of which are assigned resources with limited capacity or of limited availability. The result of such resource availability constraints is that the underlying project network is constrained in its capacity to meet the constructor’s primary objective for timely and cost-efficient project completion. The need for resource-constrained scheduling arises when there are definite limits on the amount of resources available, and the scheduling objective is to extend the project duration as little as possible beyond the original critical path duration in such a way that the resource constraints are met.
RCSP are NP-hard problems, the complexity of which increases substantially with the project network size. The number of activities and precedence relationships, as well as the number of resource types utilized in the project and the constraints imposed on them are the main sources of complexity in such schedules and add greatly to the difficulty in finding optimal time and resource allocation solutions. An optimal solution in this type of network problems can most often be found by employing computationally intensive analyses or exhaustive enumeration analyses in which all possible outcomes are evaluated. However, because of the aforementioned computational complexity, in most cases near-optimal solutions are sought by means of heuristics.
A construction process is defined as a unique collection of work tasks related to each other through a technologic structure and sequence.
Daniel W. Halpin, Planning and Analysis of Construction Operations (1992)
The resource leveling problem (RLP) is a variation of the RCSP and relates to the need for resolving over-allocations or conflicts in resource usage and/or resolving the unbalanced use of resources over time, aiming at increasing the efficiency in resource utilization. The resource leveling problem arises when there are sufficient resources available and it is necessary to reduce the fluctuations in the resource usage over the project duration. These resource fluctuations are undesirable because they often require a short-time hiring and firing policy, which negatively impact productivity at the site. The scheduling objective of the resource leveling problem is to make the resource requirements as uniform as possible or to make them match a particular nonuniform resource distribution in order to meet the needs of a given project. In resource leveling, the project duration of the original critical path remains unchanged. It should be noted, though, that besides the original critical path it is possible to make use of a prescribed deadline greater than the length of the critical path for the maximal project duration.
Ant Colony Optimization (ACO)
Ant Colony Optimization is a population-based, artificial multi-agent, general-search technique for the solution of difficult combinatorial problems with its theoretical roots based on the behavior of real ant colonies and the collective trail-laying and trail-following of its members in searching for optimal solutions in traversing multiple paths.
In essence, ACO is inspired by the foraging behavior of natural ant colonies which optimize their path from an origin (ant nest) to a destination (food source) by taking advantage of knowledge acquired by ants that previously traversed the possible paths and the pheromone trail these ants leave behind as the traverse the paths to optimal solution. In computer implementations of the ACO algorithms, artificial ants are agents and solution-construction procedures that stochastically build solutions by considering (1) artificial pheromone trails which change dynamically at run time to reflect the agents' acquired search experience, and (2) heuristic information on the problem/network being solved.
Construction scheduling exhibits many similarities to the ACO artificial agent, since the underlying network topologies and path-searching approach to longest (or shortest) path calculations are comparable.
Symeon E. Christodoulou, ASCE's Journal of Computing in Civil Engineering (2010)
We have developed software which utilizes the ACO metaheuristic in construction management and resource-constrained scheduling, providing users with an alternative way of constructing longest-path solutions in acyclic (unidirectional) network topologies. Despite the seemingly iterative approach of the ACO method, the method utilizes intelligent selection procedures to perform the optimization and arrive at the longest paths in a prescribed network topology. Ongoing work on the subject matter addresses the inclusion of resource-based scheduling techniques to account for AND/OR resource-combination requirements at the network nodes, and ways to generate total-float values for each activity (the current ACO method does not generate these values).
Since our ACO work in construction engineering and management, we have also utilized ACO in structural design (truss design optimization), water distribution networks and transportation networks.
Entropy Maximization
Entropy, in physics, is a measure of the unavailability of a system’s energy to do work, and it is central to the second law of thermodynamics which deals with physical processes and the degree of spontaneity in their occurrence (spontaneous changes occur with an increase in entropy). Entropy is thus a measure of how smooth the transformation is between different system states. The traditional definition of entropy refers to changes in the status quo of the system and it is a measure of the disorder and the amount of wasted energy during the transformation from one state to another.
Among the principal properties of entropy, two are of particular importance: subadditivity and maximality. Subadditivity, in mathematics, is a function’s property stating that the function’s value for the sum of two elements is always less than or equal to the sum of the function’s values for each element. The maximality property states that the entropy function takes the greatest value when all admissible outcomes have equal probabilities. In other words, maximal uncertainty is reached for the equiprobability distribution of possible outcomes.
The resource-leveling problem can be restated as an entropy-maximization problem.
Christodoulou et al., ASCE's Journal of Computing in Civil Engineering (2010)
Since, according to the concept of entropy, entropy is a good measure of a system’s order and stability, then a higher degree of resource-based entropy optimization should also indicate a more ordered and better-executed project. The resource-leveling problem can thus be restated as an entropy-maximization problem: how many units of a required resource should be diverted to an activity in order to maximize its entropy, subject to a limited overall resource availability within the examined time-period.
The goal, therefore, when resource-leveling projects within the aforementioned entropy framework, is to maximize the project’s total entropy, subject to the imposed resource constraints.
We, at EUPALINOS, have developed both a mathematical framework and software applications to make use of this entropy model for RCSP, and have applied the models for not only RCSP but for other contruction-related problems, such as competitive bidding, bid-unbalancing, and cash-flow optimization. Since our original work on RCSP, we have also used entropy in sensor-placement optimization, and in traffic modeling for bus-routing optimization.
