TY - GEN

T1 - Stochastic task networks trading performance for stability

AU - Mountakis, Kiriakos Simon

AU - Klos, Tomas

AU - Witteveen, Cees

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Activity network

KW - Solution robustness

KW - Stochastic scheduling

UR - http://www.scopus.com/inward/record.url?scp=85020820832&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-59776-8_25

DO - 10.1007/978-3-319-59776-8_25

M3 - Conference contribution

AN - SCOPUS:85020820832

SN - 9783319597751

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 302

EP - 311

BT - Integration of AI and OR Techniques in Constraint Programming - 14th International Conference, CPAIOR 2017, Proceedings

A2 - Salvagnin, Domenico

A2 - Lombardi, Michele

PB - Springer

T2 - 14th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, CPAIOR 2017

Y2 - 5 June 2017 through 8 June 2017

ER -