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.     

Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times

In this paper, a multi-mode resource-constrained project scheduling problem with schedule-dependent setup times is considered. A schedule-dependent setup time is defined as a setup time dependent on the assignment of resources to activities over time, when resources are, e.g., placed in different locations. In such a case, the time necessary to prepare the required resource for processing an activity depends not only on the sequence of activities but, more generally, on the locations in which successive activities are executed. Activities are non-preemptable, resources are renewable, and the objective is to minimize the project duration. A local search metaheuristic—tabu search is proposed to solve this strongly NP-hard problem, and it is compared with the multi-start iterative improvement method as well as with random sampling. A computational experiment is described, performed on a set of instances based on standard test problems constructed by the ProGen project generator. The algorithms are computationally compared, the results are analyzed and discussed, and some conclusions are given.     

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.     

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.     

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.     

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

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.     

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

Pre-emption in resource-constrained project scheduling

The Resource-Constrained Project Scheduling Project (RCPSP), together with some of its extensions, has been widely studied. A fundamental assumption in this basic problem is that activities in progress are non-preemptable. Very little effort has been made to uncover the potential benefits of discrete activity pre-emption, and the papers dealing with this issue have reached the conclusion that it has little effect on project length when constant resource availability levels are defined. In this paper we show how three basic elements of many heuristics for the RCPSP – codification, serial SGS and double justification – can be adapted to deal with interruption. The paper is mainly focussed on problem 1_PRCPSP, a generalization of the RCPSP where a maximum of one interruption per activity is allowed. However, it is also shown how these three elements can be further adapted to deal with more general pre-emptive problems. Computational experiments on the standard j30 and j120 sets support the conclusion that pre-emption does help to decrease project length when compared to the no-interruption case. They also prove the usefulness of the justification in the presence of pre-emption. The justification is a RCPS technique that can be easily incorporated into a wide range of algorithms for the RCPSP, increasing their solution quality – maintaining the number of schedules calculated.     

A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags

The paper presents an exact procedure for a general resource-constrained project scheduling problem where multiple modes are available for the performance of the individual activities and minimum as well as maximum time lags between the different activities may be given. The objective is to determine a mode and a start time for each activity such that all constraints are observed and the project duration is minimized. Project scheduling problems of this type occur, e.g. in process industries. The solution method is a depth-first search based branch-and-bound procedure. It makes use of a branching strategy where the branching rule is selected dynamically. The solution approach is an integration approach where the modes and start times are determined simultaneously. Within an experimental performance analysis this procedure is compared with existing solution procedures.     

A combined branch-and-bound and genetic algorithm based approach for a flowshop scheduling problem

In this paper, we study the application of a meta-heuristic to a two-machine flowshop scheduling problem. The meta-heuristic uses a branch-and-bound procedure to generate some information, which in turn is used to guide a genetic algorithm's search for optimal and near-optimal solutions. The criteria considered are makespan and average job flowtime. The problem has applications in flowshop environments where management is interested in reducing turn-around and job idle times simultaneously. We develop the combined branch-and-bound and genetic algorithm based procedure and two modified versions of it. Their performance is compared with that of three algorithms: pure branch-and-bound, pure genetic algorithm, and a heuristic. The results indicate that the combined approach and its modified versions are better than either of the pure strategies as well as the heuristic algorithm.     

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.     

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 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 heuristic algorithm for project scheduling with splitting allowed

In this article, we analyze the precedence diagramming method, the only published algorithm for time-only project scheduling with activity splitting allowed. The criteria used in this method (forward and backward pass computations) for deciding when an activity has to be interrupted are shown to be invalid in some situations. We look into the causes of these failures and propose new formulae that always provide feasible solutions. The new algorithm has been tested on 240 randomly generated problems ranging up to 600 activities and 7,200 precedence relationships, resulting in an average deviation from optima of less than 1 percent.     

Solving the discrete-continuous project scheduling problem via its discretization

In this paper a discrete-continuous project scheduling problem is considered. In this problem activities simultaneously require discrete and continuous resources. The processing rate of each activity depends on the amount of the continuous resource allotted to this activity at a time. All the resources are renewable ones. The activities are nonpreemtable and the objective is to minimize the makespan. Discretization of this problem leading to a classical (i.e. discrete) project scheduling problem in the multi-mode version is presented. A simulated annealing (SA) approach to solving this problem is described and tested computationally in two versions: with and without finding an optimal continuous resource allocation for the final schedule. In the former case a nonlinear solver is used for solving a corresponding convex programming problem. The results are compared with the results obtained using SA for the discrete-continuous project scheduling problem where the nonlinear solver is used for exact solving the continuous part in each iteration. The results of a computational experiment are analyzed and some conclusions are included.     

A branch-and-bound algorithm for the singly constrained assignment problem

The singly constrained assignment problem (SCAP) is a linear assignment problem (LAP) with one extra side constraint, e.g., due to a time restriction. The SCAP is, in contrast to the LAP, difficult to solve. A branch-and-bound algorithm is presented to solve the SCAP to optimality. Lower bounds are obtained by Lagrangean relaxation. Computational results show that the algorithm is able to solve different types of SCAP instances up to size n = 1000 within short running times on a standard personal computer.     

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.