On the Complexity of Scheduling to Optimize Average Response Time

DOI10.1080/02522667.1993.10699133zbMath0780.90061OpenAlexW2036411167MaRDI QIDQ4272552

William F. Klostermeyer

Publication date: 6 December 1993

Published in: Journal of Information and Optimization Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/02522667.1993.10699133

zbMATH Keywords

average response timeapproximate graph coloring

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• A better performance guarantee for approximate graph coloring
• Scheduling subject to resource constraints: Classification and complexity
• On the worst-case ratio of a compound multiprocessor scheduling algorithm
• NP-complete scheduling problems
• Improving the performance guarantee for approximate graph coloring
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Scheduling Precedence Graphs in Systems with Interprocessor Communication Times
• Scheduling Tasks with Nonuniform Deadlines on Two Processors
• Preemptive Scheduling of Uniform Processor Systems
• Complexity of Scheduling under Precedence Constraints
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

This page was built for publication: On the Complexity of Scheduling to Optimize Average Response Time