Citation
Flexibility Metrics for Time and Resource Constrained Scheduling Problems. In proceedings of the 6th Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2013), 27 - 30 Aug 2013, Ghent, Belgium, pages 555-572, 2013.
Paper
Abstract
Flexibility is an important and much wanted property of solutions to scheduling problems. Intuitively, the more ?exible a solution is, the more freedom we have in choosing a starting time of an activity without having to change the existing schedule in an essential way. In this paper we discuss ?exible solutions to the Resource Constrained Project Scheduling Problem (RCPSP). In the past years much attention has been given to a special method to obtain ?exible solutions to the RCPSP, which employs Partial Order Schedules (POS). Basically, this method reduces an RCPSP instance to a temporal constraint speci?cation, in this case an instance of the Simple Temporal Problem (STP). Instead of encoding a single solution, this STP representation encodes a number of solutions to the original RCPSP-instance. Not surprisingly, much research has been devoted to providing ?exibility metrics for the STP. After reviewing some existing ?exibility metrics, however, we conclude that these fail to capture the correlation between events speci?ed in the STP, resulting in an overestimation of the available ?exibility in the system. Therefore, we propose an intuitively more acceptable new ?exibility metric for general linear constraint systems. We also show that this ?exibility metric can be used in autonomous scheduling: Whenever a scheduling problem has to be solved by more than one independent actor, we would like to let these actors solve their part of the problem independently without violating the original constraints. This is the so-called decoupling problem. As a byproduct of the ?exibility computation, we get a decoupling of the instance almost for free: for every possible partitioning of the event space among k agents, a decoupling can be computed in linear-time. Even more importantly, we show that—contrary to popular belief—such a decomposition does not need to a?ect the ?exibility of the original linear constraint system.
You can download the pdf of this publication from here
doi
This publication does not have a doi, so we cannot provide a link to the original source
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@INPROCEEDINGS{2013-555-572-P, author = {T. Klos and M. Wilson and C. Witteveen},
title = {Flexibility Metrics for Time and Resource Constrained Scheduling Problems },
booktitle = {In proceedings of the 6th Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2013), 27 - 30 Aug 2013, Ghent, Belgium},
year = {2013},
editor = {G. Kendall and B. McCollum and G. {Venden Berghe}},
pages = {555--572},
note = {Paper},
abstract = { Flexibility is an important and much wanted property of solutions to scheduling problems. Intuitively, the more ?exible a solution is, the more freedom we have in choosing a starting time of an activity without having to change the existing schedule in an essential way. In this paper we discuss ?exible solutions to the Resource Constrained Project Scheduling Problem (RCPSP). In the past years much attention has been given to a special method to obtain ?exible solutions to the RCPSP, which employs Partial Order Schedules (POS). Basically, this method reduces an RCPSP instance to a temporal constraint speci?cation, in this case an instance of the Simple Temporal Problem (STP). Instead of encoding a single solution, this STP representation encodes a number of solutions to the original RCPSP-instance. Not surprisingly, much research has been devoted to providing ?exibility metrics for the STP. After reviewing some existing ?exibility metrics, however, we conclude that these fail to capture the correlation between events speci?ed in the STP, resulting in an overestimation of the available ?exibility in the system. Therefore, we propose an intuitively more acceptable new ?exibility metric for general linear constraint systems. We also show that this ?exibility metric can be used in autonomous scheduling: Whenever a scheduling problem has to be solved by more than one independent actor, we would like to let these actors solve their part of the problem independently without violating the original constraints. This is the so-called decoupling problem. As a byproduct of the ?exibility computation, we get a decoupling of the instance almost for free: for every possible partitioning of the event space among k agents, a decoupling can be computed in linear-time. Even more importantly, we show that—contrary to popular belief—such a decomposition does not need to a?ect the ?exibility of the original linear constraint system.},
owner = {Graham},
timestamp = {2017.01.16},
webpdf = {2013-555-572-P.pdf} }