The optimal on-line parallel machine scheduling

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

Yong He

Publication date: 21 June 2000

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

Full work available at URL: https://doi.org/10.1016/s0898-1221(00)00070-5

zbMATH Keywords

analysis of algorithmworst-case ratioon-line scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Related Items (13)

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

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

This page was built for publication: The optimal on-line parallel machine scheduling