On the optimality of the LP-based algorithm for online scheduling with GoS eligibility constraints

DOI10.1016/j.orl.2015.07.008zbMath1408.90144OpenAlexW1090409710MaRDI QIDQ1785422

An Zhang

Publication date: 28 September 2018

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2015.07.008

zbMATH Keywords

linear programmingcompetitive ratioonline schedulinggrade of service eligibility

Mathematics Subject Classification ID

Linear programming (90C05) 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 (2)

Semi-Online Hierarchical Scheduling on Two Machines for lp-Norm Load Balancing ⋮ Online fractional hierarchical scheduling on uniformly related machines

Cites Work

• Semi-online scheduling problems on two uniform machines under a grade of service provision
• Semi-online preemptive scheduling: one algorithm for all variants
• A note on hierarchical scheduling on two uniform machines
• Online hierarchical scheduling: an approach using mathematical programming
• Online and semi-online hierarchical scheduling for load balancing on uniform machines
• Improved bounds for online scheduling with eligibility constraints
• Online parallel machines scheduling with two hierarchies
• Online and semi-online scheduling of two machines under a grade of service provision
• Preemptive scheduling on a small number of hierarchical machines
• The hierarchical model for load balancing on two machines
• Online scheduling on parallel machines with two goS levels
• Preemptive online scheduling: Optimal algorithms for all speeds
• Parallel machine scheduling under a grade of service provision
• Online scheduling on uniform machines with two hierarchies
• Semi-online hierarchical scheduling problems with buffer or rearrangements
• Optimal online algorithms on two hierarchical machines with tightly-grouped processing times
• Optimal algorithms for semi-online machine covering on two hierarchical machines
• Optimal online algorithms for scheduling on two identical machines under a grade of service
• On-Line Load Balancing in a Hierarchical Server Topology
• The Competitiveness of On-Line Assignments
• A POSTERIOR COMPETITIVENESS FOR LIST SCHEDULING ALGORITHM ON MACHINES WITH ELIGIBILITY CONSTRAINTS
• Makespan minimization in online scheduling with machine eligibility

This page was built for publication: On the optimality of the LP-based algorithm for online scheduling with GoS eligibility constraints