## 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 language | English |
---|---|

Title of host publication | Integration of AI and OR Techniques in Constraint Programming - 14th International Conference, CPAIOR 2017, Proceedings |

Editors | Domenico Salvagnin, Michele Lombardi |

Publisher | Springer |

Pages | 302-311 |

Number of pages | 10 |

ISBN (Print) | 9783319597751 |

DOIs | |

Publication status | Published - 2017 |

Event | 14th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, CPAIOR 2017 - Padova, Italy Duration: 5 Jun 2017 → 8 Jun 2017 |

### Publication series

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

Volume | 10335 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

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

Country/Territory | Italy |

City | Padova |

Period | 5/06/17 → 8/06/17 |

## Keywords

- Activity network
- Solution robustness
- Stochastic scheduling