Improved bounds for online scheduling with eligibility constraints
From MaRDI portal
Publication:719259
DOI10.1016/J.TCS.2011.05.029zbMath1233.90164OpenAlexW2031740584MaRDI 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
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27)
Related Items (10)
An asymptotically optimal online algorithm to minimize the total completion time on two multipurpose machines with unit processing times ⋮ Mixed coordination mechanisms for scheduling games on hierarchical machines ⋮ Bin stretching with migration on two hierarchical machines ⋮ Semi-Online Hierarchical Scheduling on Two Machines for lp-Norm Load Balancing ⋮ Fast approximation algorithms for uniform machine scheduling with processing set restrictions ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ On the optimality of the LP-based algorithm for online scheduling with GoS eligibility constraints ⋮ Online scheduling with unit processing times and processing set restrictions ⋮ Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs ⋮ Online scheduling with migration on two hierarchical machines
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
This page was built for publication: Improved bounds for online scheduling with eligibility constraints
