Probabilistic single processor scheduling

DOI10.1016/0166-218X(90)90132-VMaRDI QIDQ912611zbMATH OpenFDO

Authors Janelle J. Harms, Charles J. Colbourn

Publication date 1990

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

nonoverlapping sets of taksPseudopolynomial time algorithmssingle processor scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• Scheduling tasks with failure probabilities to minimize expected cost
• Probabilistic Bounds on the Performance of List Scheduling
• scientific article; zbMATH DE number 67289
• Reliable assignments of processors to tasks and factoring on matroids
• Probabilistic Analysis of a Machine Scheduling Problem

Cites work

• scientific article; zbMATH DE number 3560745 (Why is no real title available?)
• scientific article; zbMATH DE number 3564698 (Why is no real title available?)
• Complexity of Matroid Property Algorithms
• Efficient algorithms for a family of matroid intersection problems
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Matroid Steiner problems, the Tutte polynomial and network reliability
• Maximum matching in a convex bipartite graph
• Minimizing maximum lateness on one machine: computational experience and some applications
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints
• Optimal assignments in an ordered set: An application of matroid theory
• Scheduling Unit–Time Tasks with Arbitrary Release Times and Deadlines
• Scheduling unit-time tasks with integer release times and deadlines
• Transversals and matroid partition
• Two-Processor Scheduling with Start-Times and Deadlines

Cited in

(6)

• Performance evaluation of schedulers in a probabilistic setting
• Reliable assignments of processors to tasks and factoring on matroids
• Scheduling tasks with failure probabilities to minimize expected cost
• Estimating the probability of meeting a deadline in schedules and plans
• Scheduling on a single processor with variable speed
• The complexity of computing the Tutte polynomial on transversal matroids

This page was built for publication: Probabilistic single processor scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q912611)