Home > Research > Publications & Outputs > Algorithmic Developments in Two-Stage Robust Sc...

Research

Associated organisational unit

Electronic data

  • 2022boldphd

    Final published version, 2.83 MB, PDF document

Text available via DOI:

View graph of relations

Algorithmic Developments in Two-Stage Robust Scheduling

Research output: Thesis › Doctoral Thesis

Published

Standard

Algorithmic Developments in Two-Stage Robust Scheduling. / Bold, Matthew.
Lancaster University, 2022. 250 p.

Research output: Thesis › Doctoral Thesis

Harvard

Bold, M 2022, 'Algorithmic Developments in Two-Stage Robust Scheduling', PhD, Lancaster University. https://doi.org/10.17635/lancaster/thesis/1668

APA

Bold, M. (2022). Algorithmic Developments in Two-Stage Robust Scheduling. [Doctoral Thesis, Lancaster University]. Lancaster University. https://doi.org/10.17635/lancaster/thesis/1668

Vancouver

Bold M. Algorithmic Developments in Two-Stage Robust Scheduling. Lancaster University, 2022. 250 p. doi: 10.17635/lancaster/thesis/1668

Author

Bold, Matthew. / Algorithmic Developments in Two-Stage Robust Scheduling. Lancaster University, 2022. 250 p.

Bibtex

@phdthesis{51b5793f0b3f44c6a3c81271aaa7bb34,
title = "Algorithmic Developments in Two-Stage Robust Scheduling",
abstract = "This thesis considers the modelling and solving of a range of scheduling problems, with a particular focus on the use of robust optimisation for scheduling in two-stage decision-making contexts.One key contribution of this thesis is the development of a new compact robustcounterpart for the resource-constrained project scheduling problem with uncertain activity durations. Resource conflicts must be resolved under the assumption of budgeted uncertainty, but start times can be determined once the activity durations become known. This formulation is also applied to the multi-mode version of this problem. In both cases, computational results show the clear dominance of the new formulation over the prior decomposition-based state-of-the-art methods.This thesis also demonstrates the first application of the recoverable robustframework to single machine scheduling. Two variants of this problem are considered, in which a first-stage schedule is constructed subject to uncertain job processing times, but can be amended in some limited way following the realisation of these processing times. The first of these problems is considered under general polyhedral uncertainty. Key results concerning the second-stage subproblem are derived, resulting in three formulations to the full problem which are compared computationally. The second of these problems considers interval uncertainty but allows for a more general recovery action. A 2-approximation is derived and the performance of a proposed greedy algorithm is examined in a series of computational experiments.In addition to these results on two-stage robust scheduling problems, a newdeterministic resource-constrained project scheduling model is developed which, for the first time, combines both generalised precedence constraints and flexible resource allocation. This model is introduced specifically for the application of scheduling the decommissioning of the Sellafield nuclear site. A genetic algorithm is proposed to solve this model, and its performance is compared against a mixedinteger programming formulation.",
author = "Matthew Bold",
year = "2022",
month = jun,
doi = "10.17635/lancaster/thesis/1668",
language = "English",
publisher = "Lancaster University",
school = "Lancaster University",

}

RIS

TY - BOOK

T1 - Algorithmic Developments in Two-Stage Robust Scheduling

AU - Bold, Matthew

PY - 2022/6

Y1 - 2022/6

N2 - This thesis considers the modelling and solving of a range of scheduling problems, with a particular focus on the use of robust optimisation for scheduling in two-stage decision-making contexts.One key contribution of this thesis is the development of a new compact robustcounterpart for the resource-constrained project scheduling problem with uncertain activity durations. Resource conflicts must be resolved under the assumption of budgeted uncertainty, but start times can be determined once the activity durations become known. This formulation is also applied to the multi-mode version of this problem. In both cases, computational results show the clear dominance of the new formulation over the prior decomposition-based state-of-the-art methods.This thesis also demonstrates the first application of the recoverable robustframework to single machine scheduling. Two variants of this problem are considered, in which a first-stage schedule is constructed subject to uncertain job processing times, but can be amended in some limited way following the realisation of these processing times. The first of these problems is considered under general polyhedral uncertainty. Key results concerning the second-stage subproblem are derived, resulting in three formulations to the full problem which are compared computationally. The second of these problems considers interval uncertainty but allows for a more general recovery action. A 2-approximation is derived and the performance of a proposed greedy algorithm is examined in a series of computational experiments.In addition to these results on two-stage robust scheduling problems, a newdeterministic resource-constrained project scheduling model is developed which, for the first time, combines both generalised precedence constraints and flexible resource allocation. This model is introduced specifically for the application of scheduling the decommissioning of the Sellafield nuclear site. A genetic algorithm is proposed to solve this model, and its performance is compared against a mixedinteger programming formulation.

AB - This thesis considers the modelling and solving of a range of scheduling problems, with a particular focus on the use of robust optimisation for scheduling in two-stage decision-making contexts.One key contribution of this thesis is the development of a new compact robustcounterpart for the resource-constrained project scheduling problem with uncertain activity durations. Resource conflicts must be resolved under the assumption of budgeted uncertainty, but start times can be determined once the activity durations become known. This formulation is also applied to the multi-mode version of this problem. In both cases, computational results show the clear dominance of the new formulation over the prior decomposition-based state-of-the-art methods.This thesis also demonstrates the first application of the recoverable robustframework to single machine scheduling. Two variants of this problem are considered, in which a first-stage schedule is constructed subject to uncertain job processing times, but can be amended in some limited way following the realisation of these processing times. The first of these problems is considered under general polyhedral uncertainty. Key results concerning the second-stage subproblem are derived, resulting in three formulations to the full problem which are compared computationally. The second of these problems considers interval uncertainty but allows for a more general recovery action. A 2-approximation is derived and the performance of a proposed greedy algorithm is examined in a series of computational experiments.In addition to these results on two-stage robust scheduling problems, a newdeterministic resource-constrained project scheduling model is developed which, for the first time, combines both generalised precedence constraints and flexible resource allocation. This model is introduced specifically for the application of scheduling the decommissioning of the Sellafield nuclear site. A genetic algorithm is proposed to solve this model, and its performance is compared against a mixedinteger programming formulation.

U2 - 10.17635/lancaster/thesis/1668

DO - 10.17635/lancaster/thesis/1668

M3 - Doctoral Thesis

PB - Lancaster University

ER -