Linear time algorithms for parallel machine scheduling

DOI10.1007/S10114-005-0838-4zbMath1151.90436OpenAlexW2045247244MaRDI QIDQ856829

Zhiyi Tan, Yong He

Publication date: 13 December 2006

Published in: Acta Mathematica Sinica. English Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10114-005-0838-4

zbMATH Keywords

schedulingworst-case ratiocomputer-aided proofdesign and analysis of algorithm

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Optimal preemptive online algorithms for scheduling with known largest size on two uniform machines
• A linear compound algorithm for uniform machine scheduling
• Semi on-line algorithms for the partition problem
• Semi on-line scheduling on two identical machines
• Semi-on-line problems on two identical machines with combined partial information
• Preemptive semi-online algorithms for parallel machine scheduling with known total size
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• An Application of Bin-Packing to Multiprocessor Scheduling
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Semi-online scheduling with decreasing job sizes

This page was built for publication: Linear time algorithms for parallel machine scheduling