Improved bounds for online scheduling with eligibility constraints

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

zbMATH Keywords

parallel machines; greedy algorithm; competitive ratio; online scheduling; eligibility constraints

Mathematics Subject Classification ID

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