Estimating the probability of meeting a deadline in schedules and plans
From MaRDI portal
Publication:2321333
DOI10.1016/J.ARTINT.2019.06.009zbMATH Open1478.90047arXiv1503.01327OpenAlexW2954015630WikidataQ127581036 ScholiaQ127581036MaRDI QIDQ2321333FDOQ2321333
Solomon E. Shimony, Gera Weiss, Liat Cohen
Publication date: 28 August 2019
Published in: Artificial Intelligence (Search for Journal in Brave)
Abstract: Given a hierarchical plan (or schedule) with uncertain task times, we propose a deterministic polynomial (time and memory) algorithm for estimating the probability 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 this problem 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 of events that do not cross deadline is #P-hard; (2)~Computing the expected makespan of a hierarchical plan is NP-hard. For the proposed approximation algorithm, we establish formal approximation bounds and show that the time and memory complexities grow polynomially with the required accuracy, the number of nodes in the plan, and with the size of the support of the random variables that represent the durations of the primitive tasks. We examine these approximation bounds empirically and demonstrate, using task networks taken from the literature, how our scheme outperforms sampling techniques and exact computation in terms of accuracy and run-time. As the empirical data shows much better error bounds than guaranteed, we also suggest a method for tightening the bounds in some cases.
Full work available at URL: https://arxiv.org/abs/1503.01327
Recommendations
Cites Work
- On computing the distribution function for the Poisson binomial distribution
- Introduction to algorithms
- Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date
- Computational Complexity
- Fast Approximation Algorithms for Knapsack Problems
- An FPTAS for #Knapsack and Related Counting Problems
- Project scheduling under uncertainty: survey and research potentials
- Approximating probabilistic inference in Bayesian belief networks is NP- hard
- Approximate counting by dynamic programming
- Discrete random bounds for general random variables and applications to reliability
- Treewidth: Characterizations, Applications, and Computations
- Title not available (Why is that?)
- The computational complexity of probabilistic inference using Bayesian belief networks
- Title not available (Why is that?)
- Title not available (Why is that?)
- Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
- Algorithms for computing the distributions of sums of discrete random variables
- Complexity results for HTN planning
- Disregarding Duration Uncertainty in Partial Order Schedules? Yes, We Can!
- Importance sampling algorithms for Bayesian networks: principles and performance
- Title not available (Why is that?)
- Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks
- Probabilistic inference in multiply connected belief networks using loop cutsets
- Generating the maximum of independent identically distributed random variables
- Title not available (Why is that?)
- Average execution times of series-parallel networks
Cited In (1)
Uses Software
This page was built for publication: Estimating the probability of meeting a deadline in schedules and plans
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2321333)
