Probabilistic single processor scheduling

DOI10.1016/0166-218X(90)90132-VzbMath0698.68035MaRDI QIDQ912611

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)

Related Items

The complexity of computing the Tutte polynomial on transversal matroids

Cites Work

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