Linear time algorithms for parallel machine scheduling

DOI10.1007/S10114-005-0838-4MaRDI QIDQ856829zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Algorithmic Applications in Management
• scientific article; zbMATH DE number 2219502
• Parallel algorithms for solution of problems in scheduling theory
• Minimizing the makespan in nonpreemptive parallel machine scheduling problem
• Parallel machines scheduling with nonsimultaneous machine available time

Cites work

• scientific article; zbMATH DE number 1559404 (Why is no real title available?)
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• A linear compound algorithm for uniform machine scheduling
• An Application of Bin-Packing to Multiprocessor Scheduling
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Optimal preemptive online algorithms for scheduling with known largest size on two uniform machines
• Preemptive semi-online algorithms for parallel machine scheduling with known total size
• 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
• Semi-online scheduling with decreasing job sizes

Cited in

(6)

• Algorithmic Applications in Management
• scientific article; zbMATH DE number 5951383 (Why is no real title available?)
• Parallel machine scheduling, linear programming, and parameter list scheduling heuristics
• Time optimal linear schedules for algorithms with uniform dependencies
• scientific article; zbMATH DE number 2219502 (Why is no real title available?)
• Approximation and Online Algorithms

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

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