Joint chance constrained probabilistic simple temporal networks via column generation (extended abstract)

Probabilistic Simple Temporal Networks (PSTN) are used to represent scheduling problems under uncertainty. In a temporal network that is strongly controllable (SC) there exists a concrete schedule that is robust to any uncertainty. In this paper we introduce the Joint Chance-Constrained PSTN (JCC-PSTN) which lifts assumptions of independence and Boole's inequality, which are typically leveraged in PSTN literature. We solve the problem of JCC-PSTN SC via a column generation procedure and find that our approach offers on average a 10 times reduction in cost versus using Boole’s inequality