The optimal on-line parallel machine scheduling

DOI10.1016/S0898-1221(00)00070-5zbMath0973.90033MaRDI QIDQ1568731

Yong He

Publication date: 21 June 2000

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

zbMATH Keywords

analysis of algorithm; worst-case ratio; on-line scheduling

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90B35: Deterministic scheduling theory in operations research

Related Items

A POSTERIOR COMPETITIVENESS FOR LIST SCHEDULING ALGORITHM ON MACHINES WITH ELIGIBILITY CONSTRAINTS, SEMI-ON-LINE SCHEDULING PROBLEM FOR MAXIMIZING THE MINIMUM MACHINE COMPLETION TIME ON THREE SPECIAL UNIFORM MACHINES, Semi-online scheduling with bounded job sizes on two uniform machines, An on-line scheduling problem of parallel machines with common maintenance time, Optimal semi-online preemptive algorithms for machine covering on two uniform machines, Optimal preemptive online algorithms for scheduling with known largest size on two uniform machines, Optimal semi-online algorithms for machine covering, Extension of algorithm list scheduling for a semi-online scheduling problem, Ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times, Semi-on-line problems on two identical machines with combined partial information, Semi-online scheduling jobs with tightly-grouped processing times on three identical machines, Preemptive machine covering on parallel machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounds for nonpreemptive scheduling of jobs with similar processing times on multiprocessor systems using the LPT-algorithm
• The exact LPT-bound for maximizing the minimum completion time
• Semi on-line scheduling on two identical machines
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• A Better Algorithm for an Ancient Scheduling Problem
• Bounds for Certain Multiprocessing Anomalies