A lower bound for on-line scheduling on uniformly related machines

DOI10.1016/S0167-6377(99)00062-0zbMath0958.90043OpenAlexW1990290269MaRDI QIDQ1970423

Leah Epstein, Jiří Sgall

Publication date: 18 April 2001

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(99)00062-0

zbMATH Keywords

preemptionuniformly related machineson-line scheduling of jobs

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (21)

Separating online scheduling algorithms with the relative worst order ratio ⋮ Online algorithms for scheduling with machine activation cost on two uniform machines ⋮ Lower bounds for online makespan minimization on a small number of related machines ⋮ Preemptive online scheduling with rejection of unit jobs on two uniformly related machines ⋮ A Lower Bound for the On-Line Preemptive Machine Scheduling with ℓ p Norm ⋮ Heuristics and augmented neural networks for task scheduling with non-identical machines ⋮ Unnamed Item ⋮ Preemptive scheduling on a small number of hierarchical machines ⋮ Optimal on-line algorithms to minimize makespan on two machines with resource augmentation ⋮ Robust algorithms for preemptive scheduling ⋮ Optimal semi-online algorithms for preemptive scheduling problems with inexact partial information ⋮ Semi-online preemptive scheduling: one algorithm for all variants ⋮ Randomized on-line scheduling on two uniform machines ⋮ Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios ⋮ Preemptive online scheduling: Optimal algorithms for all speeds ⋮ Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes ⋮ Optimal and online preemptive scheduling on uniformly related machines ⋮ New algorithms for related machines with temporary jobs. ⋮ A lower bound on deterministic online algorithms for scheduling on related machines without preemption ⋮ Preemptive machine covering on parallel machines ⋮ Optimal preemptive semi-online scheduling to minimize makespan on two related machines

Cites Work

• Unnamed Item
• Unnamed Item
• A lower bound for randomized on-line multiprocessor scheduling
• Online algorithms. The state of the art
• Preemptive on-line scheduling for two uniform processors
• An optimal algorithm for preemptive on-line scheduling
• A Level Algorithm for Preemptive Scheduling
• Preemptive Scheduling of Uniform Processor Systems
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• On-Line Load Balancing for Related Machines

This page was built for publication: A lower bound for on-line scheduling on uniformly related machines