Chance-constrained Scheduling via Conflict-directed Risk Allocation

Temporal uncertainty in large-scale logistics forces one to trade off between lost efficiency through built-in slack and costly replanning when deadlines are missed. Due to the dif-ficulty of reasoning about such likelihoods and consequences, a computational framework is needed to quantify and bound the risk of violating scheduling requirements. This work ad-dresses the chance-constrained scheduling problem, where actions ’ durations are modeled probabilistically. Our solution method uses conflict-directed risk allocation to efficiently compute a scheduling policy. The key insight, compared to previous work in probabilistic scheduling, is to decouple the reasoning about temporal and risk constraints. This de-composes the problem into a separate master and subprob-lem, which can be iteratively solved much quicker. Through a set of simulated car-sharing scenarios, it is empirically shown that conflict-directed risk allocation computes solu-tions nearly an order of magnitude faster than prior art does, which considers all constraints in a single lump-sum opti-mization