Improved bounds for online scheduling with eligibility constraints

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

zbMATH Keywords

parallel machinesgreedy algorithmcompetitive ratioonline schedulingeligibility constraints

Mathematics Subject Classification ID

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