General parametric scheme for the online uniform machine scheduling problem with two different speeds

DOI10.1016/j.ipl.2018.01.009zbMath1476.90115MaRDI QIDQ1707972

Alain Quilliot, Vladimir Kotov, Aliaksandr Nekrashevich, Alexandre Dolgui

Publication date: 4 April 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.01.009

zbMATH Keywords

scheduling; online algorithms; approximation algorithms

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

68W25: Approximation algorithms

68W27: Online algorithms; streaming algorithms

Related Items

A survey on makespan minimization in semi-online environments, Performance analysis of fixed assignment policies for stochastic online scheduling on uniform parallel machines

Cites Work

• Unnamed Item
• Online scheduling with one rearrangement at the end: revisited
• Online scheduling with rearrangement on two related machines
• Online scheduling on two uniform machines subject to eligibility constraints
• A new algorithm for online uniform-machine scheduling to minimize the makespan
• An efficient algorithm for semi-online multiprocessor scheduling with given total processing time
• Online scheduling with reassignment on two uniform machines
• Online scheduling on two uniform machines to minimize the makespan
• Preemptive on-line scheduling for two uniform processors
• Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines
• An efficient algorithm for bin stretching
• Semi-online scheduling on two uniform processors
• Bounds for List Schedules on Uniform Processors
• An On-Line Algorithm for Some Uniform Processor Scheduling
• Bounds on Multiprocessing Timing Anomalies