Improved bounds for online scheduling with eligibility constraints
From MaRDI portal
Publication:719259
DOI10.1016/j.tcs.2011.05.029zbMath1233.90164MaRDI QIDQ719259
Kangbok Lee, Soo Y. Chang, Kyungkuk Lim
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
Semi-Online Hierarchical Scheduling on Two Machines for lp-Norm Load Balancing, Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs, Makespan minimization in online scheduling with machine eligibility, Mixed coordination mechanisms for scheduling games on hierarchical machines, Bin stretching with migration on two hierarchical machines, 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, Online scheduling with migration on two hierarchical machines, Online scheduling with unit processing times and processing set restrictions
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