Tight upper bounds for semi-online scheduling on two uniform machines with known optimum

DOI10.1007/s10100-017-0481-zzbMath1390.90310OpenAlexW2625359686WikidataQ47555800 ScholiaQ47555800MaRDI QIDQ1642847

Zsolt Tuza, György Dósa, Armin Fügenschuh, Krzysztof Węsek, Zhiyi Tan

Publication date: 15 June 2018

Published in: CEJOR. Central European Journal of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10100-017-0481-z

zbMATH Keywords

schedulingmakespan minimizationmixed-integer linear programmingsemi-online algorithm

Mathematics Subject Classification ID

Mixed integer programming (90C11) Deterministic scheduling theory in operations research (90B35) Online algorithms; streaming algorithms (68W27)

Related Items

A survey on makespan minimization in semi-online environments, Single workgroup scheduling problem with variable processing personnel, Tight lower bounds for semi-online scheduling on two uniform machines with known optimum

Cites Work

• Unnamed Item
• Unnamed Item
• Semi-online scheduling problems on a small number of machines
• Two uniform machines with nearly equal speeds: unified approach to known sum and known optimum in semi on-line scheduling
• Online bin stretching with bunch techniques
• Semi-on-line multiprocessor scheduling with given total processing time
• Semi on-line scheduling on three processors with known sum of the tasks
• Two semi-online scheduling problems on two uniform machines
• Semi on-line algorithms for the partition problem
• Bin stretching revisited
• On-line scheduling revisited
• A two-phase algorithm for bin stretching with stretching factor 1.5
• Online bin stretching with three bins
• The on-line multiprocessor scheduling problem with known sum of the tasks
• Semi-online scheduling on two uniform processors
• A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines without Preemption
• Geometric representation for semi on-line scheduling on uniform processors
• Better Bounds for Online Scheduling
• On-Line Load Balancing for Related Machines
• Bounds on Multiprocessing Timing Anomalies
• On-line bin-stretching