Stochastic task networks trading performance for stability

Kiriakos Simon Mountakis, Tomas Klos, Cees Witteveen*

*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

Abstract

This paper concerns networks of precedence constraints between tasks with random durations, known as stochastic task networks, often used to model uncertainty in real-world applications. In some applications, we must associate tasks with reliable start-times from which realized start-times will (most likely) not deviate too far. We examine a dispatching strategy according to which a task starts as early as precedence constraints allow, but not earlier than its corresponding planned release-time. As these release-times are spread farther apart on the time-axis, the randomness of realized start-times diminishes (i.e. stability increases). Effectively, task start-times becomes less sensitive to the outcome durations of their network predecessors. With increasing stability, however, performance deteriorates (e.g. expected makespan increases). Assuming a sample of the durations is given, we define an LP for finding release-times that minimize the performance penalty of reaching a desired level of stability. The resulting LP is costly to solve, so, targeting a specific part of the solution-space, we define an associated Simple Temporal Problem (STP) and show how optimal release-times can be constructed from its earliest-start-time solution. Exploiting the special structure of this STP, we present our main result, a dynamic programming algorithm that finds optimal release-times with considerable efficiency gains.

Original languageEnglish
Title of host publicationIntegration of AI and OR Techniques in Constraint Programming - 14th International Conference, CPAIOR 2017, Proceedings
EditorsDomenico Salvagnin, Michele Lombardi
PublisherSpringer
Pages302-311
Number of pages10
ISBN (Print)9783319597751
DOIs
Publication statusPublished - 2017
Event14th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, CPAIOR 2017 - Padova, Italy
Duration: 5 Jun 20178 Jun 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10335 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, CPAIOR 2017
Country/TerritoryItaly
CityPadova
Period5/06/178/06/17

Keywords

  • Activity network
  • Solution robustness
  • Stochastic scheduling

Fingerprint

Dive into the research topics of 'Stochastic task networks trading performance for stability'. Together they form a unique fingerprint.

Cite this