---
title: "Estimating the Probability of Meeting a Deadline in Hierarchical Plans"
authors:
  - "Liat Cohen"
  - "Solomon Eyal Shimony"
  - "Gera Weiss"
doi: ""
url: "https://ijcai.org/proceedings/2015/222"
pdf: "https://ijcai.org/proceedings/2015/0222.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "1551-1556"
track: "Main Track"
keywords:
---

# Estimating the Probability of Meeting a Deadline in Hierarchical Plans

Liat Cohen, Solomon Eyal Shimony, Gera Weiss

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 1551-1556.

## 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.