On the optimality of list scheduling for online uniform machines scheduling

DOI10.1007/S11590-011-0335-XzbMath1259.90034OpenAlexW1986998019MaRDI QIDQ694192

Fangqiu Han, Yang Yang, Zhiyi Tan

Publication date: 11 December 2012

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-011-0335-x

zbMATH Keywords

competitive analysisonlineuniform machines

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (3)

A survey on makespan minimization in semi-online environments ⋮ Lower bounds for online makespan minimization on a small number of related machines ⋮ A lower bound on deterministic online algorithms for scheduling on related machines without preemption

Cites Work

• Unnamed Item
• Unnamed Item
• A new algorithm for online uniform-machine scheduling to minimize the makespan
• Preemptive online scheduling: Optimal algorithms for all speeds
• Tighter approximation bounds for LPT scheduling in two special cases
• Preemptive on-line scheduling for two uniform processors
• New lower and upper bounds for on-line scheduling
• An optimal algorithm for preemptive on-line scheduling
• Optimal Algorithms for the Online Time Series Search Problem
• Bounds for List Schedules on Uniform Processors
• An On-Line Algorithm for Some Uniform Processor Scheduling
• Improved Bounds for the Online Scheduling Problem
• On-Line Load Balancing for Related Machines
• Bounds for Certain Multiprocessing Anomalies
• Randomized on-line scheduling on two uniform machines

This page was built for publication: On the optimality of list scheduling for online uniform machines scheduling