Advanced search
1 file | 6.77 MB Add to list

Algorithms and datasets for project scheduling problems

Rob Van Eynde (UGent)
(2022)
Author
Promoter
(UGent)
Organization
Abstract
This 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.

Downloads

  • (...).pdf
    • full text (Published version)
    • |
    • UGent only
    • |
    • PDF
    • |
    • 6.77 MB

Citation

Please use this url to cite or link to this publication:

MLA
Van Eynde, Rob. Algorithms and Datasets for Project Scheduling Problems. Ghent University. Faculty of Economics and Business Administration, 2022.
APA
Van Eynde, R. (2022). Algorithms and datasets for project scheduling problems. Ghent University. Faculty of Economics and Business Administration, Ghent, Belgium.
Chicago author-date
Van Eynde, Rob. 2022. “Algorithms and Datasets for Project Scheduling Problems.” Ghent, Belgium: Ghent University. Faculty of Economics and Business Administration.
Chicago author-date (all authors)
Van Eynde, Rob. 2022. “Algorithms and Datasets for Project Scheduling Problems.” Ghent, Belgium: Ghent University. Faculty of Economics and Business Administration.
Vancouver
1.
Van Eynde R. Algorithms and datasets for project scheduling problems. [Ghent, Belgium]: Ghent University. Faculty of Economics and Business Administration; 2022.
IEEE
[1]
R. Van Eynde, “Algorithms and datasets for project scheduling problems,” Ghent University. Faculty of Economics and Business Administration, Ghent, Belgium, 2022.
@phdthesis{8735267,
  abstract     = {{This 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.}},
  author       = {{Van Eynde, Rob}},
  language     = {{eng}},
  pages        = {{XIV, 209}},
  publisher    = {{Ghent University. Faculty of Economics and Business Administration}},
  school       = {{Ghent University}},
  title        = {{Algorithms and datasets for project scheduling problems}},
  year         = {{2022}},
}