TY - JOUR

T1 - Probabilistic single processor scheduling

AU - Harms, Janelie J.

AU - Colbourn, Charles J.

N1 - Funding Information:
Research of the first author is supported in part by an NSERC Postgraduate Scholarship and by the Institute for Computer Research, University of Waterloo. Research of the second author is supported by NSERC Canada under grant number A0579.

PY - 1990/5

Y1 - 1990/5

N2 - In the probabilistic single processor scheduling problem, there are n tasks, each with a start time, a length, a deadline, and a probability of occurrence. When tasks occur independently with the known probabilities, the task reliability is the probability that all occurring tasks can be completed, each by its deadline. The processor reliability is the probability that the occurring tasks keep the processor as busy as possible. A set of tasks is nonoverlapping whenever for any two tasks, if the start time of the first precedes the start time of the second, the deadline of the first is no later than the deadline of the second. Pseudopolynomial time algorithms are developed for computing task and processor reliabilities for nonoverlapping sets of tasks; when all tasks have unit length, these algorithms are polynomial time. Efficient algorithms for counting bases, circuits, and cocircuits in doubly convex scheduling matroids are also developed.

AB - In the probabilistic single processor scheduling problem, there are n tasks, each with a start time, a length, a deadline, and a probability of occurrence. When tasks occur independently with the known probabilities, the task reliability is the probability that all occurring tasks can be completed, each by its deadline. The processor reliability is the probability that the occurring tasks keep the processor as busy as possible. A set of tasks is nonoverlapping whenever for any two tasks, if the start time of the first precedes the start time of the second, the deadline of the first is no later than the deadline of the second. Pseudopolynomial time algorithms are developed for computing task and processor reliabilities for nonoverlapping sets of tasks; when all tasks have unit length, these algorithms are polynomial time. Efficient algorithms for counting bases, circuits, and cocircuits in doubly convex scheduling matroids are also developed.

UR - http://www.scopus.com/inward/record.url?scp=45149135845&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=45149135845&partnerID=8YFLogxK

U2 - 10.1016/0166-218X(90)90132-V

DO - 10.1016/0166-218X(90)90132-V

M3 - Article

AN - SCOPUS:45149135845

SN - 0166-218X

VL - 27

SP - 101

EP - 112

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-2

ER -