On the Complexity of Scheduling to Optimize Average Response Time

DOI10.1080/02522667.1993.10699133MaRDI QIDQ4272552zbMATH OpenOpenAlexFDO

Authors 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

approximate graph coloringaverage response time

Mathematics Subject Classification ID

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

Recommendations

• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Scheduling jobs that arrive over time
• Minimizing average completion time in the presence of release dates
• scientific article; zbMATH DE number 1559529
• Task Scheduling in Networks

Cites work

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

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

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