An On-Line Algorithm for Some Uniform Processor Scheduling

DOI10.1137/S0097539799527969MaRDI QIDQ4388879zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• A new algorithm for online uniform-machine scheduling to minimize the makespan
• Preemptive on-line scheduling for two uniform processors
• On-line preemptive scheduling on uniform machines
• Scheduling uniform machines on-line requires nondecreasing speed ratios
• Online scheduling on \(m\) uniform machines to minimize total (weighted) completion time

Cited in

(27)

• The price of anarchy on uniformly related machines revisited
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• Competitive ratio of list scheduling on uniform machines and randomized heuristics
• On the optimality of list scheduling for online uniform machines scheduling
• Online scheduling on three uniform machines
• Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios
• A parametric scheme for online uniform-machine scheduling to minimize the makespan
• A survey on makespan minimization in semi-online environments
• General parametric scheme for the online uniform machine scheduling problem with two different speeds
• Preemptive on-line scheduling for two uniform processors
• Tighter approximation bounds for LPT scheduling in two special cases
• Semi-online scheduling on two uniform parallel machines with initial lookahead
• New lower and upper bounds for on-line scheduling
• scientific article; zbMATH DE number 1817675 (Why is no real title available?)
• Improved scheduling in rings
• The Price of Anarchy on Uniformly Related Machines Revisited
• Starting time minimization for the maximum job variant
• Performance analysis of fixed assignment policies for stochastic online scheduling on uniform parallel machines
• An on-line algorithm for some uniform processor Scheduling
• Online scheduling on \(m\) uniform machines to minimize total (weighted) completion time
• A new algorithm for online uniform-machine scheduling to minimize the makespan
• scientific article; zbMATH DE number 1474842 (Why is no real title available?)
• Online Scheduling on a CPU-GPU Cluster
• Online scheduling on uniform machines with two hierarchies
• Uniform processor scheduling problem with nonsimultaneous available time
• Increasing Machine Speed in On-Line Scheduling of Weighted Unit-Length Jobs in Slotted Time
• Online scheduling of mixed CPU-GPU jobs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4388879)