A column generation approach to correlated simple temporal networks

Murray, Andrew and Arulselvan, Ashwin and Cashmore, Michael and Roper, Marc and Frank, Jeremy; Koenig, Sven and Stern, Roni and Vallati, Mauro, eds. (2023) A column generation approach to correlated simple temporal networks. In: Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling. Proceedings of the International Conference on Automated Planning and Scheduling . AAAI Press, CZE, pp. 295-303. ISBN 9781577358817 (https://doi.org/10.1609/icaps.v33i1.27207)

[thumbnail of Murray-etal-ICAPS-2023-A-column-generation-approach-to-correlated-simple-temporal-networks]
Preview
 Text. Filename: Murray-etal-ICAPS-2023-A-column-generation-approach-to-correlated-simple-temporal-networks.pdf
Accepted Author Manuscript
License: Strathprints license 1.0
Download (1MB)| Preview

Abstract

Probabilistic Simple Temporal Networks (PSTN) represent scheduling problems under temporal uncertainty. Strong controllability (SC) of PSTNs involves finding a schedule to a PSTN that maximises the probability that all constraints are satisfied (robustness). Previous approaches to this problem assume independence of probabilistic durations, and approximate the risk by bounding it above using Boole’s inequality. This gives no guarantee of finding the schedule optimising robustness, and fails to consider correlations between probabilistic durations that frequently arise in practical applications. In this paper, we formally define the Correlated Simple Temporal Network (Corr-STN) which generalises the PSTN by removing the restriction of independence. We show that the problem of Corr-STN SC is convex for a large class of multivariate (log-concave) distributions. We then introduce an algorithm capable of finding optimal SC schedules to Corr-STNs, using the column generation method. Finally, we validate our approach on a number of Corr-STNs and find that our method offers more robust solutions when compared with prior approaches.

CORE (COnnecting REpositories)