Approximate solution of a resource-constrained scheduling problem

This paper is devoted to the approximate solution of a strongly NP-hard resource-constrained scheduling problem which arises in relation to the operability of certain high availability real time distributed systems. We present an algorithm based on the simulated annealing metaheuristic and, building on previous research on exact solution methods, extensive computational results demonstrating its practical ability to produce acceptable solutions, in a precisely defined sense. Additionally, our experiments are in remarkable agreement with certain theoretical properties of our simulated annealing scheme. The paper concludes with a short discussion on further research. This research was supported in part by Association Nationale de la Recherche Technique grant CIFRE-121/2004.     

The multi-mode resource-constrained project scheduling problem with generalized precedence relations

In this paper, we tackle the challenging problem of scheduling activities to minimize the project duration, in which the activities (a) are subject to generalized precedence relations, (b) require units of multiple renewable, non-renewable and doubly constrained resources for which a limited availability is imposed, and (c) can be performed in one of several different ways, reflected in multiple activity scenarios or modes. These multiple modes give rise to several kinds of trade-offs (time/resource, time/cost and resource/resource trade-offs) which allow for a more efficient allocation and use of resources. We present a local search-based solution methodology which is able to handle many real-life project scheduling characteristics such as time-varying resource requirements and availabilities, activity ready times, due dates and deadlines, activity overlaps, activity start time constraints and other types of temporal constraints.     

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.     

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.     

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.     

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 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 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.     

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 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.     

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.     

On a resource-constrained scheduling problem with application to distributed systems reconfiguration

This paper is devoted to the study of a resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high availability real-time distributed systems. Informally, this problem consists, starting from an arbitrary initial distribution of processes on the processors of a distributed system, in finding the least disruptive sequence of operations (non-impacting process migrations or temporary process interruptions) at the end of which the system ends up in another predefined arbitrary state. The main constraint is that the capacity of the processors must not be exceeded during the reconfiguration. After a brief survey of the literature, we prove the NP-hardness of the problem and exhibit a few polynomial special cases. We then present a branch-and-bound algorithm for the general case along with computational results demonstrating its practical relevance. The paper is concluded by a discussion on further research.     

Minimizing total weighted late work in the resource-constrained project scheduling problem

This paper deals with resource-constrained project scheduling problem under the weighted late work criterion. Late work objective functions estimate the quality of a schedule based on durations of late parts of activities, not taking into account the amount of delay for fully late activities. It is assume that a project contains activities interrelated by finish-to-start type precedence relations with time lag of zero, which require one or more constrained renewable resources. The objective is to schedule each activity such that the total weighted late work is minimized. The problem has been formulated using a linear integer programming model and solved by the CPLEX. Also, a set of priority rules have been designed to quickly generate a set of initial solutions. In order to solve the problem optimally, a depth-first branch-and-bound algorithm is applied based on idea of minimal delaying alternatives. The branching order of nodes that belong to the same level of the search tree is determined on the basis of the developed priority rules. This results in generation six different versions of the branch-and-bound algorithm. Computational results on randomly generated problem sets are provided to analyze the efficiency of the priority rules and the branch-and-bound algorithm.     

Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements

We consider the resource-constrained scheduling problem when each job’s resource requirements remain constant over its processing time. We study a time-indexed formulation of the problem, providing facet-defining inequalities for a projection of the resulting polyhedron that exploit the resource limitations inherent in the problem. Lifting procedures are then provided for obtaining strong valid inequalities for the original polyhedron. Computational results are presented to demonstrate the strength of these inequalities.     

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.     

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.