An On-Line Algorithm for Some Uniform Processor Scheduling

DOI10.1137/S0097539799527969zbMath0914.90164OpenAlexW2036209007MaRDI QIDQ4388879

Rongheng Li, Li-Jie Shi

Publication date: 10 May 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539799527969

zbMATH Keywords

list schedulinguniform machineson-line scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items (14)

A survey on makespan minimization in semi-online environments ⋮ A new algorithm for online uniform-machine scheduling to minimize the makespan ⋮ Performance analysis of fixed assignment policies for stochastic online scheduling on uniform parallel machines ⋮ ONLINE SCHEDULING OF MIXED CPU-GPU JOBS ⋮ Online scheduling on uniform machines with two hierarchies ⋮ The price of anarchy on uniformly related machines revisited ⋮ Competitive ratio of list scheduling on uniform machines and randomized heuristics ⋮ General parametric scheme for the online uniform machine scheduling problem with two different speeds ⋮ On the optimality of list scheduling for online uniform machines scheduling ⋮ Online Scheduling on a CPU-GPU Cluster ⋮ The Price of Anarchy on Uniformly Related Machines Revisited ⋮ Starting time minimization for the maximum job variant ⋮ Tighter approximation bounds for LPT scheduling in two special cases ⋮ Online scheduling on three uniform machines

This page was built for publication: An On-Line Algorithm for Some Uniform Processor Scheduling