Improved bounds for online scheduling with eligibility constraints
From MaRDI portal
Publication:719259
DOI10.1016/j.tcs.2011.05.029zbMath1233.90164MaRDI QIDQ719259
Kangbok Lee, Kyungkuk Lim, Soo Y. Chang
Publication date: 10 October 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.05.029
90B35: Deterministic scheduling theory in operations research
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
68W27: Online algorithms; streaming algorithms
Related Items
Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs, Makespan minimization in online scheduling with machine eligibility, Fast approximation algorithms for uniform machine scheduling with processing set restrictions, On the optimality of the LP-based algorithm for online scheduling with GoS eligibility constraints, An asymptotically optimal online algorithm to minimize the total completion time on two multipurpose machines with unit processing times
Cites Work
- Unnamed Item
- Unnamed Item
- Coordination mechanisms with hybrid local policies
- Online hierarchical scheduling: an approach using mathematical programming
- Scheduling jobs with equal processing times subject to machine eligibility constraints
- A fast preemptive scheduling algorithm with release times and inclusive processing set restrictions
- Online scheduling on two uniform machines subject to eligibility constraints
- Online and semi-online scheduling of two machines under a grade of service provision
- Online scheduling on parallel machines with two goS levels
- New algorithms for an ancient scheduling problem.
- Scheduling parallel machines with inclusive processing set restrictions and job release times
- A better lower bound for on-line scheduling
- On-line load balancing
- Online algorithms: a survey
- Parallel machine scheduling of machine-dependent jobs with unit-length.
- On-line scheduling revisited
- Parallel machine scheduling under a grade of service provision
- New lower and upper bounds for on-line scheduling
- Parallel machine scheduling with nested job assignment restrictions
- Parallel machine scheduling with nested processing set restrictions
- On-Line Load Balancing in a Hierarchical Server Topology
- Scheduling parallel machines with inclusive processing set restrictions
- An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
- Better Bounds for Online Scheduling
- The Competitiveness of On-Line Assignments
- A POSTERIOR COMPETITIVENESS FOR LIST SCHEDULING ALGORITHM ON MACHINES WITH ELIGIBILITY CONSTRAINTS
- Improved Bounds for the Online Scheduling Problem
- A Better Algorithm for an Ancient Scheduling Problem
- Parallel machine scheduling with job assignment restrictions
- Bounds for Certain Multiprocessing Anomalies
- Makespan minimization in online scheduling with machine eligibility