0000000000192091
AUTHOR
Vicente Valls
Justification technique generalizations
The justification technique was introduced various decades ago for the resource-constrained project scheduling problem, although it has rarely been used with the problem. Justification is a simple and quick technique which when applied to schedules produces a new schedule that is, at most, as long as the original schedule — and often shorter. A recent article (Valls et al, 2005), showed that incorporating justification in heuristic algorithms can produce a substancial improvement in the results obtained. These results have motivated us to generalise this technique in order to study it in greater depth. This paper proposes distinct forms and generalisations for the justification technique an…
Integer Preemption Problems
A fundamental assumption in the basic RCPSP is that activities in progress are non-preemptable. Some papers reveal the potential benefits of allowing activity interruptions in the schedule when the objective is the makespan minimization. In this chapter we consider the Maxnint_PRCPSP in which it is assumed that activities can be interrupted at any integer time instant with no cost incurred, that each activity can be split into a maximum number of parts, and that each part has a minimum duration established. We show how some procedures developed for the RCPSP can be adapted to work with the Maxnint_PRCPSP and we introduce some procedures specifically designed for this problem. Furthermore, p…
Minimizing weighted tardiness of jobs with stochastic interruptions in parallel machines
Abstract In this paper, we address the problem of minimizing expected total weighted tardiness of jobs that have stochastic interruptions and that are processed on a set of parallel machines. Our research generalizes the problem of scheduling parallel machines to minimize total weighted tardiness. The proposed solution method is based on the scatter search methodology and implements an innovative structured combination procedure. Extensive computational testing with more than 400 problem instances shows the merit of the proposed solution method.
Pre-emption in resource-constrained project scheduling
Abstract 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 foc…
Time and work generalised precedence relationships in project scheduling with pre-emption: An application to the management of Service Centres
Abstract In this paper we present an application of project scheduling concepts and solution procedures for the solution of a complex problem that comes up in the daily management of many company Service Centres. The real problem has been modelled as a multi-mode resource-constrained project scheduling problem with pre-emption, time and work generalised precedence relationships with minimal and maximal time lags between the tasks and due dates. We present a complete study of work GPRs which includes proper definitions, a new notation and all possible conversions amongst them. Computational results that show the efficiency of the proposed hybrid genetic algorithm and the advantages of allowi…
Looking for the best modes helps solving the MRCPSP/max
The multi-mode resource-constrained project scheduling problem with minimum and maximum time lags MRCPSP/max is a very general project scheduling problem with multiple execution modes per activity, renewable and non-renewable resources and minimum and maximum time lags between activities. In this paper, we describe SA-EVA, an algorithm for the problem. SA-EVA first searches for the best mode for each activity, without considering renewable resources. In this phase a simulated annealing is applied. Once a mode vector has been chosen, the problem reduces to the RCPSP/max, which SA-EVA solves with EVA, an algorithm designed in Ballestin et al. [2009. An evolutionary algorithm for the resource-…
Pre-processing techniques for resource allocation in the heterogeneous case
The Heterogeneous Resource Allocation Problem (HRAP) deals with the allocation of resources, whose units do not all share the same characteristics, to an established plan of activities. Each activity requires one or more units of each resource which possess particular characteristics, and the objective is to find the minimum number of resource units of each type, necessary to carry out all the activities within the plan, in such a way that two activities whose processing overlaps in time do not have the same resource unit assigned. The HRAP is an NP-Complete problem and it is possible to optimally solve medium-sized HRAP instances in a reasonable time. The objective of this work is to devel…
A double genetic algorithm for the MRCPSP/max
This paper presents a heuristic solution procedure for a very general resource-constrained project scheduling problem. Here, multiple execution modes are available for the individual activities of the project. In addition, minimum as well as maximum time lags between different activities may be given. The objective is to determine a mode and a start time for each activity such that the temporal and resource constraints are met and the project duration is minimised. Project scheduling problems of this type occur e.g. in process industries. The heuristic is a two-phased genetic algorithm with different representation, fitness, crossover operator, etc., in each of them. One of the contribution…
A multi-objective approach for a project scheduling problem with due dates and temporal constraints infeasibilities
In this paper, we study a multi-mode resource-constrained project scheduling problem (RCPSP) which considers time and work generalised precedence relationships with minimal and maximal time lags and due dates where each activity requires only one unit of resource (e.g. a worker, a machine, etc.). To find a feasible solution for this problem is NP-hard and therefore for instances where a feasible solution has not been found, an appropriate real-life approach would consist of providing the decision-maker with a collection of quality solutions with a trade-off between due dates and temporal constraints violations. We propose a multi-objective evolutionary algorithm for the generation of an app…
Scheduling projects with limited number of preemptions
A recent paper (Ballestin F, Valls V, Quintanilla S. Preemption in resource-constrained project scheduling. European Journal of Operational Research 2008;189:1136-152) revealed the potential benefits of allowing one interruption when scheduling activities in a resource-constrained project. This paper further investigates the effect of interruption on project length in more general cases. To achieve this, a new model that covers most practical applications of discrete activity preemption is proposed and a metaheuristic algorithm for the problem is developed. Computational experiments on the standard j120 and j30 sets generated using ProGen study the difference in makespan between allowing m …
Project Scheduling with Stochastic Activity Interruptions
In this chapter we address the problem of scheduling the activities of a resource-constrained project, some of which may be interrupted by an uncertain amount of time. The resources may be, for example, machines in a jobshop, computers with specialized software packages (as those needed for engineering designs), or highly specialized technicians.
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.
A hybrid genetic algorithm for the resource-constrained project scheduling problem
Abstract 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 j…
A Population-Based Approach to the Resource-Constrained Project Scheduling Problem
We present a population-based approach to the RCPSP. The procedure has two phases. The first phase handles the initial construction of a population of schedules and these are then evolved until high quality solutions are obtained. The evolution of the population is driven by the alternative application of an efficient improving procedure for locally improving the use of resources, and a mechanism for combining schedules that blends scatter search and path relinking characteristics. The objective of the second phase is to explore in depth those vicinities near the high quality schedules. Computational experiments on the standard j120 set, generated using ProGen, show that our algorithm produ…
Due Dates and RCPSP
Due dates are an essential feature of real projects, but little effort has been made in studying the RCPSP with due dates in the activities. This paper tries to bridge this gap by studying two problems: the TardinessRCPSP, in which the objective is total tardiness minimization and the DeadlineRCPSP, in which the due dates are strict (deadlines) and the objective is makespan minimization. The first problem is NP-hard and the second is much harder, since finding a feasible solution is already NP-hard. This paper has three objectives: Firstly to compare the performance on both problems of well-known RCPSP heuristics - priority rules, sampling procedures and metaheuristics - with new versions w…
Static and dynamic policies with RFID for the scheduling of retrieval and storage warehouse operations
Warehouses are essential components of logistics and supply chains. The performance of warehouse operations significantly affects the efficiency of the whole chain it belongs to. Radio frequency identification (RFID) is an emerging technology capable of providing real-time information about the location and properties of tagged object(s), such as people, equipment or products. The objective of this article is threefold, to propose and compare different offline and online policies for the scheduling of warehouse operations, to design a tool that allows the decision maker to compare policies and environments without putting them into practice, and to study the benefits that can be obtained if…
A Modified Tabu Thresholding Approach for the Generalised Restricted Vertex Colouring Problem
We present a modification of the Tabu Thresholding (TT) approach and apply it to the solution of the generalised restricted vertex colouring problem. Both the bounded and unbounded cases are treated. In our algorithms, the basic TT elements are supplemented with an evaluation function that depends on the best solution obtained so far, together with a mechanism which reinforces the aggressive search in the improving phase, and new diversification strategies which depend on the state of the search. The procedure is illustrated through the solution of the problem of minimising the number of workers in a heterogeneous workforce.
Resource-constrained project scheduling: A critical activity reordering heuristic
Abstract In this paper, we present a new metaheuristic algorithm for the resource-constrained project-scheduling problem. The procedure is a non-standard implementation of fundamental concepts of tabu search without explicitly using memory structures embedded in a population-based framework. The procedure makes use of a fan search strategy to intensify the search, whereas a strategic oscillation mechanism loosely related to the forward/backward technique provides the necessary diversification. Our implementation employs the topological order (TO) representation of schedules. To explore the TO vector space we introduce three types of moves, two of them based on the concept of relative critic…
A graph colouring model for assigning a heterogeneous workforce to a given schedule
Abstract We analyze a heterogeneous workforce assignment problem in which the minimum number of workers required to carry out a machine load plan is calculated. The problem is formulated as a restricted vertex colouring problem and a branch and bound algorithm is presented. The special characteristics of the graph to be coloured allow an efficient implementation of the branch and bound. Computational results show that the algorithm can solve problems of 50 activities, 5, 10 and 15 machines and between 2 to 15 different types of workers in just a few seconds.
Justification and RCPSP: A technique that pays
Abstract The objective of this paper is to show that justification is a simple technique that can be easily incorporated in diverse algorithms for the resource-constrained project scheduling problem––improving the quality of the schedules generated without generally requiring more computing time. The results of incorporating this technique in 22 different algorithms are shown. Fifteen of the new algorithms that use double justification outperform seven of the best heuristic algorithms that do not use justification. The tests have been performed on the standard test set j120 for the RCPSP generated using ProGen.
Skilled workforce scheduling in Service Centres
Abstract The Skilled Workforce Project Scheduling Problem (SWPSP) is a complex problem of task scheduling and resource assignment that comes up in the daily management of many company Service Centres (SC). The SWPSP considers many real characteristics faced daily by the SC: client-company service quality agreements that establish maximum dates for the beginning and the end of tasks with penalties for delays, criticality levels indicating the client-priority in processing each task, generalized precedence relationships that can produce cycle structures, time period and percentage time lags and variable task durations depending on the worker executing the task. Furthermore, the SC workforce i…
A tabu thresholding algorithm for arc crossing minimization in bipartite graphs
Acyclic directed graphs are commonly used to model complex systems. The most important criterion to obtain a readable map of an acyclic graph is that of minimizing the number of arc crossings. In this paper, we present a heuristic for solving the problem of minimizing the number of arc crossings in a bipartite graph. It consists of a novel and easier implementation of fundamental tabu search ideas without explicit use of memory structures (a tabu thresholding approach). Computational results are reported on a set of 250 randomly generated test problems. Our algorithm has been compared with the two best heuristics published in the literature and with the optimal solutions for the test proble…