Estimating the probability of meeting a deadline in schedules and plans

DOI10.1016/J.ARTINT.2019.06.009MaRDI QIDQ2321333zbMATH OpenOpenAlexWikidataFDO

Authors Liat Cohen, Solomon E. Shimony, Gera Weiss

Publication date 28 August 2019

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.01327

zbMATH Keywords

planrandom variablesapproximationmakespanscheduledeadline

Mathematics Subject Classification ID

Approximation algorithms (68W25) Stochastic scheduling theory in operations research (90B36)

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.

Recommendations

• AI*IA 2005: Advances in Artificial Intelligence
• Probabilistic single processor scheduling
• As soon as probable: optimal scheduling under stochastic uncertainty
• scientific article
• Probabilistic Bounds on the Performance of List Scheduling

Cites work

• scientific article; zbMATH DE number 5547872 (Why is no real title available?)
• scientific article; zbMATH DE number 4053069 (Why is no real title available?)
• scientific article; zbMATH DE number 43880 (Why is no real title available?)
• scientific article; zbMATH DE number 2038904 (Why is no real title available?)
• scientific article; zbMATH DE number 1775053 (Why is no real title available?)
• Algorithms for computing the distributions of sums of discrete random variables
• An FPTAS for #Knapsack and Related Counting Problems
• Approximate counting by dynamic programming
• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• Average execution times of series-parallel networks
• Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks
• Complexity results for HTN planning
• Computational Complexity
• Discrete random bounds for general random variables and applications to reliability
• Disregarding Duration Uncertainty in Partial Order Schedules? Yes, We Can!
• Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date
• Fast Approximation Algorithms for Knapsack Problems
• Generating the maximum of independent identically distributed random variables
• Importance sampling algorithms for Bayesian networks: principles and performance
• Introduction to algorithms
• On computing the distribution function for the Poisson binomial distribution
• Probabilistic inference in multiply connected belief networks using loop cutsets
• Project scheduling under uncertainty: survey and research potentials
• Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
• The computational complexity of probabilistic inference using Bayesian belief networks
• Treewidth: Characterizations, Applications, and Computations

Cited in

(2)

• Efficiently approximating the probability of deadline misses in real-time systems
• Efficient optimal Kolmogorov approximation of random variables

Describes a project that uses

Uses Software

• SHOP2

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)