ML Anthology

Estimating the Probability of Meeting a Deadline in Hierarchical Plans

Liat Cohen, Solomon Eyal Shimony, Gera Weiss
IJCAI 2015 pp. 1551-1557
/ijcai/2015/cohen2015ijcai-estimating/

Abstract

Given a hierarchical plan (or schedule) with uncertain task times, we may need to determine the probability that a given plan will satisfy a given deadline. This problem is shown to be NP-hard for series-parallel hierarchies. We provide a polynomial-time approximation algorithm for it. Computing the expected makespan of an hierarchical plan is also shown to be NP-hard. We examine the approximation bounds empirically and demonstrate where our scheme is superior to sampling and to exact computation.

PDF IJCAI Semantic Scholar

Cite

Text

Cohen et al. "Estimating the Probability of Meeting a Deadline in Hierarchical Plans." International Joint Conference on Artificial Intelligence, 2015.

Markdown

[Cohen et al. "Estimating the Probability of Meeting a Deadline in Hierarchical Plans." International Joint Conference on Artificial Intelligence, 2015.](https://mlanthology.org/ijcai/2015/cohen2015ijcai-estimating/)

BibTeX

@inproceedings{cohen2015ijcai-estimating,
  title     = {{Estimating the Probability of Meeting a Deadline in Hierarchical Plans}},
  author    = {Cohen, Liat and Shimony, Solomon Eyal and Weiss, Gera},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2015},
  pages     = {1551-1557},
  url       = {https://mlanthology.org/ijcai/2015/cohen2015ijcai-estimating/}
}