31 research outputs found
New summary measures and datasets for the multi-project scheduling problem
No full textIn recent years, more researchers have devoted their attention to the resource-constrained multi-project scheduling problem, resulting in a growing body of knowledge on solution procedures. A key factor in the comparison of these procedures is the availability of benchmark datasets that cover a large part of the feature space. Otherwise, one risks that the conclusions from experiments on these sets do not hold when they are repeated on a different set. In this paper we propose new multi-project datasets that contain instances with a wide variety of characteristics. We first develop several new measures that describe three types of portfolio characteristics, two of the three types are not present in any of the existing datasets. Second, an algorithm is developed that can generate instances with the desired parameter values in a controlled manner. With this procedure, we create three datasets that each focus on one of the characteristics and a fourth dataset that contains all combinations. The computational results show (a) that these sets cover a significantly larger part of the feature space than existing benchmark libraries and (b) that they are more challenging for advanced algorithms.We acknowledge the support provided by the Special Research Fund [BOF grant no. DOC014-18 Van Eynde] and the National Bank of Belgium for providing the first author with a pre-doctoral fellowship. The computational resources (Stevin Supercomputer Infrastructure) and services used in this work were provided by the VSC (Flemish Supercomputer Center), funded by Ghent University, FWO and the Flemish Government department EWI
COMPASS: A social-ecological macroeconomic model for guiding pathways to equitable human wellbeing within planetary boundaries
No full textThe documentation of the sustainability, wellbeing, economy, and demographics modules of the model developed for the ToBe project
Algorithms and datasets for project scheduling problems
No full textThis dissertation studies several problems in the field of project scheduling. A project is a unique endeavor consisting of a set of tasks that need to be executed. In project scheduling the goal is to create a good schedule such that all activities are executed while multiple types of restrictions are respected. The most common objective is to find the schedule with the shortest completion time or makespan. The dissertation focusses on three key aspects in the literature: solution algorithms, summary measures and benchmark datasets. The main focus in literature is the development of solution algorithms to create schedules that are as good as possible. However, these algorithms need to be tested on benchmark datasets, if these are biased or do not contain all types of projects, one risks obtaining wrong conclusions from computational experiments. In order to create good datasets, one requires summary measures to describe the essential characteristics of projects.
In Chapter 2 a new solution algorithm for the discrete time/cost trade-off problem is developed. The algorithm uses modular decomposition to split the problem in smaller subproblems which can be solved more efficiently. The computational experiments show that it improves upon an existing algorithm from literature but does not outperform the best procedure available.
Chapter 3 proposes a theoretical framework to predict how complex a project will be to solve. This framework calculates three different summary measures that can be used as indicators for complexity. The computational experiments show that the framework is a good predictor of complexity and that focusing on the precedence and resource characteristics of the project gives the best results. In Chapter 4 we execute an extensive evaluation of the most popular summary measures in literature. Additionally, we propose new alternatives, some of which are based on the framework from Chapter 3. Based on the experiments we provide recommendations on which measures are best suited for different purposes.
The last part of the dissertation addresses the multi-project scheduling problem, in which a portfolio of projects needs to be scheduled. In Chapter 5 we propose new solution algorithms that schedule the portfolio in a decoupled way, keeping track of the individual project structures in the complete portfolio. Furthermore, we critically evaluate the existing summary measures and datasets from literature and propose adaptations to both the measures and datasets. In Chapter 6 we create a wide variety of new summary measures for multi-project data, which allow researchers and practitioners to describe new characteristics in their portfolio. Next, we introduce an algorithm to generate artificial instances with these measures. The computational experiments show that these datasets are more diverse than those that are present in literature
A theoretical framework for instance complexity of the resource-constrained project scheduling problem
No full textThe resource-constrained project scheduling problem (RCPSP) addresses the problem of constructing a schedule with minimum makespan for a set of activities, subject to precedence and resource constraints. Recent research introduced a data set with small instances that cannot be solved by the state-of-the-art algorithms, revealing a gap in our understanding of instance complexity. We propose a new theoretical framework for the instance complexity for the RCPSP, consecutively incorporating precedence constraints, resource constraints, and activity durations. Our approach contributes to the existing knowledge base in two ways. First, it is independent from solution algorithms, which enables generalisable conclusions. Second, the theoretical perspective enables a deeper understanding of the drivers of instance complexity. We evaluate the performance of our approach with a series of computational experiments. These show that our framework is a strong discriminator between easy and hard instances and explains a large fraction of CPU times of optimal solution algorithms
A reduction tree approach for the discrete time/cost trade-off problem
No full textThe Discrete Time/Cost Trade-Off Problem is a well studied problem in the project scheduling literature. Each activity has multiple execution modes, a solution is obtained by selecting a mode for each activity. In this manuscript we propose an exact algorithm to obtain the complete curve of non-dominated time/cost alternatives for the project. Our algorithm is based on the network reduction approach in which the project is reduced to a singular activity. We develop the reduction tree, a new datastructure that tracks the modular decomposition structure of an instance at each iteration of the reduction sequence. We show how it is related to the complexity graph of the instance. Several exact and heuristic algorithms to construct a good reduction tree are proposed. Our computational experiments show that the use of the reduction tree provides significant speedups when compared to the existing reduction plan approach. Although the new approach does not outperform the best performing branch-and-bound procedure from the literature, the experiments show that incorporating modular decomposition can provide significant performance improvements for solution algorithms, showing potential for developing improved hybridized procedures to solve this challenging problem type
Making marine sediment extraction sustainable by mitigation of related processes with potential negative impacts
No full textNo abstracts are to be cited without prior reference to the author.Conveners: Ad Stolk (the Netherlands), Keith Cooper (UK), Michel Desprez (France).CM 2016/K:346. Changes in bottom shear stress, due to aggregate extraction, in the area of the Hinder Banks (Belgian Continental Shelf). D. Van den Eynde, M. Baeye, M. Fettweis, F. Francken and V.R.M. Van LanckerCM 2016/K:638. Combining measured and visually observed granulometric characteristics in updatable voxel models of seabed sediment. Sytze van HeterenCM 2016/K:275. Developments in cumulative impact assessment from a marine minerals extraction view. Jan A. van DalfsenCM 2016/K:94. Ecosystem based design rules for sand extraction sites. Maarten de Jong, Martin Baptist, Bas Borsje, Daan RijksCM 2016/K:417. Identifying, assessment and adaptive environmental management of environmental effects between UK dredging areas and herring Clupea harengus spawning habitat. Ian Reach, Phil Latto, Dafydd Lloyd Jones, Rob Langman, Caroline Chambers, Iain Warner, Mark RussellCM 2016/K:317. Impact of dredging activity on the distribution and diet of demersal fish species in a commercial marine aggregate extraction site of the eastern Channel (Dieppe, France). Michel DesprezCM 2016/K:641. Make marine sediment extraction sustainable by mitigation of related processes with potential negative impacts. Ad Stolk CM 2016/K:640. Large scale sand extraction. Monitoring effects on morphology and ecosystem. Ad StolkCM 2016/K:172. Marine aggregate dredging: a new monitoring approach to meet the needs of the Marine Strategy Framework Directive. Keith Cooper, Jon Barry, Clare MasonCM 2016/K:639. Marine sand and gravel extraction for Helsinki harbor – monitoring the impact of the extraction works. Jyrki HämäläinenCM 2016/K:469. Minimisation of the impact of sand extraction on the Belgian part of the North Sea by the introduction of a newly defined reference surface. Koen Degrendele, Marc RocheCM 2016/K:412. MSFD-compliant investigative monitoring of the effects of intensive aggregate extraction on a far offshore sandbank, Belgian part of the North Sea. V.R.M. Van Lancker, M. Baeye, D. Evangelinos, G. Montereale‐Gavazzi, N. Terseleer, D. Van den EyndeCM 2016/K:617. Optimization of monitoring and modelling frameworks to mitigate negative effects of aggregate extraction, Belgian part of the North Sea. N. Terseleer, M. Roche, K. Degrendele, D. Van den Eynde, V.R.M. Van LanckerCM 2016/K:431. Quantifying the resource potential of Quaternary sands on the Belgian Continental Shelf: a 3D voxel modelling approach. Vasileios Hademenos, Lars Kint, Tine Missiaen, Jan Stafleu, Vera Van LanckerCM 2016/K:380. Relation between dredging intensity and frequency and its impact on a benthic sandy habitat. Annelies De Backer, Kris HostensCM 2016/K:494. Robust Marine Protected Area designation through the use of marine aggregate sector environmental data. Ian Reach, Stuart Lowe, Mark Russell, Andrew Bellamy, Joseph Holcroft, Louise Mann, Dafydd Lloyd Jones, Rob LangmanCM 2016/K:315. The role of extraction strategy on the recovery of biological communities in two French sites of marine aggregate extraction in the eastern Channel. Management implications for sustainability. Michel Desprez, Gwenola de Roton, Bastien Chouquet, Pierre Balay</p
On the complexity of efficient multi-skilled team composition
No full textWorkers that master multiple skills increase the flexibility and the working range of teams in organizations. Efficient multi-skilled team formation or workforce composition is therefore paramount for the organization’s success. In this paper, we study various multi-skilled workforce formation problems that are complementary to problems in the scheduling literature. The goal of these problems is to design a set of multi-skilled workers (or resources) that can fulfill a certain skill demand. More specifically, we investigate the complexity of problems that minimize the skill availability or the size of the workforce. Next, we look at the impact of specific skill and worker characteristics on the complexity of these problems. We propose a set of fixed individual multi-skilled workforce problems, in which the number of available skills per skill type or the number of mastered skills per worker is defined upfront. Furthermore, we introduce and discuss the complexity of fixed total multi-skilled workforce problems in which either the total skill availability or the workforce size is fixed and the other quantity is minimized. We conclude this paper by applying the presented problems to real-life projects and by performing computational experiments that analyze the empirical hardness of the multi-skilled workforce problems
Correction to: on the summary measures for the resource-constrained project scheduling problem
No full textReducing the feasible solution space of resource-constrained project instances
No full textWe introduce three definitions of project instance equivalence.
A reduction of the feasible search space is obtained using new theorems.
A large computational experiment on different datasets is carried out.•
New best known solutions are found and shared.This paper present an instance transformation procedure to modify known instances of the resource-constrained project scheduling problem to make them easier to solve by heuristic and/or exact solution algorithms. The procedure makes use of a set of transformation rules that aim at reducing the feasible search space without excluding at least one possible optimal solution. The procedure will be applied to a set of 11,183 instances and it will be shown by a set of experiments that these transformations lead to 110 improved lower bounds, 16 new and better schedules (found by three meta-heuristic procedures and a set of branch-and-bound procedures) and even 64 new optimal solutions which were never not found before.All computational experiments were carried out using the Stevin Supercomputer Infrastructure at Ghent University (Belgium), funded by Ghent University, Belgium, the Hercules Foundation, Belgium and the Flemish Government – department EWI, Belgium . We also acknowledge the help van Dr. Rob Van Eynde clarifying the feasible set indicators
On the summary measures for the resource-constrained project scheduling problem
No full textThe resource-constrained project scheduling problem is a widely studied problem in the literature. The goal is to construct a schedule for a set of activities, such that precedence and resource constraints are respected and that an objective function is optimized. In project scheduling literature, summary measures are often used as a tool to evaluate the performance of algorithms and to analyze instances and datasets. They can be classified in two groups, network measures describe the precedence constraints of a project, while resource measures focus on the resource constraints of the instance. In this manuscript we make an exhaustive evaluation of the summary measures for project scheduling. We provide an overview of the most prevalent measures and also introduce some new ones. For our tests we combine different datasets from the literature and generate a new set with diverse characteristics. We evaluate the performance of the summary measures on three dimensions: consistency, instance complexity and algorithm selection. We conclude by providing an overview of which measures are best suited for each of the three investigated dimensions
