English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given a hierarchical plan (or schedule) with uncertain task times, we proposea deterministic polynomial (time and memory) algorithm for estimating theprobability that its meets a deadline, or, alternately, that its {\em makespan}is less than a given duration. Approximation is needed as it is known that thisproblem is NP-hard even for sequential plans (just, a sum of random variables).In addition, we show two new complexity results: (1) Counting the number ofevents that do not cross deadline is \#P-hard; (2)~Computing the expectedmakespan of a hierarchical plan is NP-hard. For the proposed approximationalgorithm, we establish formal approximation bounds and show that the time andmemory complexities grow polynomially with the required accuracy, the number ofnodes in the plan, and with the size of the support of the random variablesthat represent the durations of the primitive tasks. We examine theseapproximation bounds empirically and demonstrate, using task networks takenfrom the literature, how our scheme outperforms sampling techniques and exactcomputation in terms of accuracy and run-time. As the empirical data shows muchbetter error bounds than guaranteed, we also suggest a method for tighteningthe bounds in some cases.

Estimating the Probability of Meeting a Deadline in Hierarchical Plans