Two uniform machines with nearly equal speeds: unified approach to known sum and known optimum in semi on-line scheduling

DOI10.1007/s10878-009-9265-2zbMath1319.90030MaRDI QIDQ491212

Zsolt Tuza, György Dósa, M. Grazia Speranza

Publication date: 24 August 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-009-9265-2

zbMATH Keywords

competitive analysis; uniform machines; semi-online scheduling

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

68W27: Online algorithms; streaming algorithms

Related Items

Semi-online scheduling problems on two uniform machines under a grade of service provision, Online bin stretching with bunch techniques

Cites Work

• Unnamed Item
• Unnamed Item
• Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines
• Two semi-online scheduling problems on two uniform machines
• Semi on-line algorithms for the partition problem
• Semi on-line scheduling on two identical machines
• Bin stretching revisited
• Semi-on-line scheduling on two parallel processors with an upper bound on the items
• Semi-online algorithms for parallel machine scheduling problems
• Semi-online scheduling on two uniform processors
• Bounds for List Schedules on Uniform Processors
• Bounds for Certain Multiprocessing Anomalies
• Randomized on-line scheduling on two uniform machines
• Semi on-line scheduling on two parallel processors with known sum and lower bound on the size of the tasks
• On-line bin-stretching