A hybrid metaheuristic for the resource-constrained project scheduling problem

This study presents a hybrid metaheuristic ANGEL for the resource-constrained project scheduling problem (RCPSP). ANGEL combines ant colony optimization (ACO), genetic algorithm (GA) and local search strategy. The procedures of ANGEL are as follows. First, ACO searches the solution space and generates activity lists to provide the initial population for GA. Next, GA is executed and the pheromone set in ACO is updated when GA obtains a better solution. When GA terminates, ACO searches again by using a new pheromone set. ACO and GA search alternately and cooperatively in the solution space. This study also proposes an efficient local search procedure which is applied to yield a better solution when ACO or GA obtains a solution. A final search is applied upon the termination of ACO and GA. The experimental results of ANGEL on the standard sets of the project instances show that ANGEL is an effective method for solving the RCPSP.     

A hybrid genetic algorithm for the resource-constrained project scheduling problem

In this paper we propose a Hybrid Genetic Algorithm (HGA) for the Resource-Constrained Project Scheduling Problem (RCPSP). HGA introduces several changes in the GA paradigm: a crossover operator specific for the RCPSP; a local improvement operator that is applied to all generated schedules; a new way to select the parents to be combined; and a two-phase strategy by which the second phase re-starts the evolution from a neighbour’s population of the best schedule found in the first phase. The computational results show that HGA is a fast and high quality algorithm that outperforms all state-of-the-art algorithms for the RCPSP known by the authors of this paper for the instance sets j60 and j120. And that it is competitive with other state-of-the-art heuristics for the instance set j30.     

An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances

In this paper, an overview is presented of the existing metaheuristic solution procedures to solve the multi-mode resource-constrained-project scheduling problem, in which multiple execution modes are available for each of the activities of the project. A fair comparison is made between the different metaheuristic algorithms on the existing benchmark datasets and on a newly generated dataset. Computational results are provided and recommendations for future research are formulated.     

A survey of variants and extensions of the resource-constrained project scheduling problem

The resource-constrained project scheduling problem (RCPSP) consists of activities that must be scheduled subject to precedence and resource constraints such that the makespan is minimized. It has become a well-known standard problem in the context of project scheduling which has attracted numerous researchers who developed both exact and heuristic scheduling procedures. However, it is a rather basic model with assumptions that are too restrictive for many practical applications. Consequently, various extensions of the basic RCPSP have been developed. This paper gives an overview over these extensions. The extensions are classified according to the structure of the RCPSP. We summarize generalizations of the activity concept, of the precedence relations and of the resource constraints. Alternative objectives and approaches for scheduling multiple projects are discussed as well. In addition to popular variants and extensions such as multiple modes, minimal and maximal time lags, and net present value-based objectives, the paper also provides a survey of many less known concepts.     

A branch-and-bound algorithm for the resource-constrained project scheduling problem

We describe a time-oriented branch-and-bound algorithm for the resource-constrained project scheduling problem which explores the set of active schedules by enumerating possible activity start times. The algorithm uses constraint-propagation techniques that exploit the temporal and resource constraints of the problem in order to reduce the search space. Computational experiments with large, systematically generated benchmark test sets, ranging in size from thirty to one hundred and twenty activities per problem instance, show that the algorithm scales well and is competitive with other exact solution approaches. The computational results show that the most difficult problems occur when scarce resource supply and the structure of the resource demand cause a problem to be highly disjunctive.     

A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem

We consider the multi-mode resource-constrained project scheduling problem (MRCPSP), where a task has different execution modes characterized by different resource requirements. Due to the nonrenewable resources and the multiple modes, this problem is NP-hard; therefore, we implement an evolutionary algorithm looking for a feasible solution minimizing the makespan.     

A multiple-tree search procedure for the resource-constrained project scheduling problem

For over three decades, researchers have sought effective solution procedures for PERT/CPM types of scheduling problems under conditions of limited resource availability. This paper presents a procedure for this problem which takes advantage of the emerging technology provided by multiple parallel processors to find and verify an optimal schedule for a project under conditions of multiple resource constraints. In our approach, multiple solutions trees are searched simultaneously in the quest for a minimum duration schedule. Global upper and lower bound information in common memory is shared among processors, enabling one or several processors to prune potentially significant portions of its search tree based upon bounds discovered by a processor using a different search tree. Computational experience is reported both for problems in which resources are available in constant amounts per period, as well as the much more difficult problem in which the resources available are allowed to vary over the schedule horizon (e.g., travel, sick leave, assignment to other tasks or projects, and so forth). The modular multiple-tree search procedure described in this paper is quite general, permitting most types of existing serial search strategies to be adapted to this approach where multiple processors are available.     

A constraint programming approach for the resource-constrained project scheduling problem

A “pure” Constraint Programming approach for the Resource-Constrained Project Scheduling Problem (RCPSP) is presented. Our basic idea was to substitute the resource constraints by a set of “sub-constraints” generated as needed. Each of these sub-constraints corresponds to a set of tasks that cannot be executed together without violating one of the resource constraints. A filtering algorithm for these sub-constraints has been developed. When applied to the initial resource constraints together with known filtering algorithms, this new filtering algorithm provides very good numerical results.     

Proactive policies for the stochastic resource-constrained project scheduling problem

The resource-constrained project scheduling problem involves the determination of a schedule of the project activities, satisfying the precedence and resource constraints while minimizing the project duration. In practice, activity durations may be subject to variability. We propose a stochastic methodology for the determination of a project execution policy and a vector of predictive activity starting times with the objective of minimizing a cost function that consists of the weighted expected activity starting time deviations and the penalties or bonuses associated with late or early project completion. In a computational experiment, we show that our procedure greatly outperforms existing algorithms described in the literature.     

A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem

This paper presents a genetic algorithm for solving the resource-constrained project scheduling problem. The innovative component of the algorithm is the use of a magnet-based crossover operator that can preserve up to two contiguous parts from the receiver and one contiguous part from the donator genotype. For this purpose, a number of genes in the receiver genotype absorb one another to have the same order and contiguity they have in the donator genotype. The ability of maintaining up to three contiguous parts from two parents distinguishes this crossover operator from the powerful and famous two-point crossover operator, which can maintain only two contiguous parts, both from the same parent. Comparing the performance of the new procedure with that of other procedures indicates its effectiveness and competence.     

Solving resource-constrained project scheduling problem with evolutionary programming

This paper presents an evolutionary programming (EP)-based approach to solving the resource-constrained project scheduling problem (RCPSP), a well-known NP-hard problem in scheduling, with minimization of project duration as the objective subject to precedence and resource constraints. The individual representation of EP for the problem is based on random keys. The serial generation scheme is used in the decoding scheme to generate the project plan. Experimental analyses are presented to investigate the performance of the proposed EP-based methodology, including comparison of the four variants of EP, namely, CEP, FEP, MCEP and IMCEP, with each other and GA to find the best variant of EP for the RCPSP, and comparison of this best variant of EP (MCEP) with other approaches using the J30 standard instances set in PSPLIB. The computational results validate the effectiveness of the proposed algorithm.     

A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem

In this paper we present a genetic algorithm for the multi-mode resource-constrained project scheduling problem (MRCPSP), in which multiple execution modes are available for each of the activities of the project. We also introduce the preemptive extension of the problem which allows activity splitting (P-MRCPSP). To solve the problem, we apply a bi-population genetic algorithm, which makes use of two separate populations and extend the serial schedule generation scheme by introducing a mode improvement procedure. We evaluate the impact of preemption on the quality of the schedule and present detailed comparative computational results for the MRCPSP, which reveal that our procedure is amongst the most competitive algorithms.     

A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations

We present an optimal solution procedure for the resource-constrained project scheduling problem (RCPSP) with generalized precedence relations (RCPSP-GPR) with the objective of minimizing the project makespan. The RCPSPGPR extends the RCPSP to arbitrary minimal and maximal time lags between the starting and completion times of activities. The proposed procedure is suited for solving a general class of project scheduling problems and allows for arbitrary precedence constraints, activity ready times and deadlines, multiple renewable resource constraints with time-varying resource requirements and availabilities, several types of permissible and mandatory activity overlaps and multiple projects. It can be extended to other regular and non-regular measures of performance. Essentially, the procedure is a depth-first branch-and-bound algorithm in which the nodes in the search tree represent the original project network extended with extra precedence relations to resolve a number of resource conflicts. These conflicts are resolved using the concept of minimal delaying modes, which is an extension of the notion of minimal delaying alternatives for the RCPSP. Several bounds and dominance rules are used to fathom large portions of the search tree. Extensive computational experience is reported.     

A faster exact method for solving the robust multi-mode resource-constrained project scheduling problem

This paper presents a mixed-integer linear programming formulation for the multi-mode resource-constrained project scheduling problem with uncertain activity durations. We consider a two-stage robust optimisation approach and find solutions that minimise the worst-case project makespan, whilst assuming that activity durations lie in a budgeted uncertainty set. Computational experiments show that this easy-to-implement formulation is many times faster than the current state-of-the-art solution approach for this problem, whilst solving over 40% more instances to optimality over the same benchmarking set.     

Activity list representation for a generalization of the resource-constrained project scheduling problem

Most of the real life scheduling problems include several constraints in addition to the precedence and resource constraints considered in the resource-constrained project scheduling problem (RCPSP  ). In this paper, we define a generalization of the (RCPSP)$(\mathit{RCPSP})$ with a wide class of additional constraints, including (but not limited to): a pair of activities must be separated by at least a given duration; a subset of activities cannot be processed simultaneously; an activity cannot start before a particular period; an activity cannot be scheduled in a particular time window; there are resource constraints with varying required and available quantities. We show that for this generalization the activity list and the activity set list representations can be used as efficiently as in the (RCPSP)$(\mathit{RCPSP})$ and that by using these representations the optimal solution can always be reached.     

PROGRESS: Optimally solving the generalized resource-constrained project scheduling problem

This paper deals with the generalized resource-constrained project scheduling problem (GRCPSP) which extends the well-known resource-constrained project scheduling problem (RCPSP) by considering job specific release and due dates, non-negative minimum start-to-start time lags as well as time-varying resource availabilities. The structure of the project is represented by an acyclic network diagram. Though the extensions are of high practical importance, only a few exact solution procedures have been presented in the literature so far. Therefore, a new exact procedure PROGRESS is developed which includes new dominance rules as well as enhancements of existing ones. For evaluating the efficiency experimentally, new GRCPSP instances with 30 and 60 jobs are considered which extend the standard benchmark sets for the RCPSP generated by ProGen. PROGRESS shows superior performance when applied to the GRCPSP and is also very competitive in comparison to approaches proposed for the RCPSP.     

An automatic algorithm selection approach for the multi-mode resource-constrained project scheduling problem

This paper investigates the construction of an automatic algorithm selection tool for the multi-mode resource-constrained project scheduling problem (MRCPSP). The research described relies on the notion of empirical hardness models. These models map problem instance features onto the performance of an algorithm. Using such models, the performance of a set of algorithms can be predicted. Based on these predictions, one can automatically select the algorithm that is expected to perform best given the available computing resources. The idea is to combine different algorithms in a super-algorithm that performs better than any of the components individually. We apply this strategy to the classic problem of project scheduling with multiple execution modes. We show that we can indeed significantly improve on the performance of state-of-the-art algorithms when evaluated on a set of unseen instances. This becomes important when lots of instances have to be solved consecutively. Many state-of-the-art algorithms perform very well on a majority of benchmark instances, while performing worse on a smaller set of instances. The performance of one algorithm can be very different on a set of instances while another algorithm sees no difference in performance at all. Knowing in advance, without using scarce computational resources, which algorithm to run on a certain problem instance, can significantly improve the total overall performance.     

An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem

In this paper a branch-and-bound procedure is described for scheduling project activities subject to precedence and resource constraints, where activities can be preempted at any discrete time instant and where the objective is to minimize the project duration. The procedure is based on a depth-first solution strategy in which nodes in the solution tree represent resource and precedence feasible partial schedules. Branches emanating from a parent node correspond to exhaustive and minimal combinations of activities, the delay of which resolves resource conflicts at each parent node. A precedence based lower bound and several dominance rules are introduced in order to restrict the growth of the solutions tree. The solution procedure has been programmed in the C language and extensive computational experience is reported.