Online hierarchical scheduling: an approach using mathematical programming

DOI10.1016/J.TCS.2009.08.014zbMath1207.90058OpenAlexW2010486202MaRDI QIDQ621843

Zhiyi Tan, An Zhang

Publication date: 28 January 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.08.014

zbMATH Keywords

schedulingcompetitive ratiomathematical programminghierarchyonline

Mathematics Subject Classification ID

Nonlinear programming (90C30) Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Online algorithms; streaming algorithms (68W27)

Related Items (16)

Total completion time minimization in online hierarchical scheduling of unit-size jobs ⋮ Total completion time minimization scheduling on two hierarchical uniform machines ⋮ Semi-online hierarchical scheduling for \(l_p\)-norm load balancing with buffer or rearrangements ⋮ Bin stretching with migration on two hierarchical machines ⋮ Semi-Online Hierarchical Scheduling on Two Machines for lp-Norm Load Balancing ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ TWO APPROXIMATION SCHEMES FOR SCHEDULING ON PARALLEL MACHINES UNDER A GRADE OF SERVICE PROVISION ⋮ Fast approximation algorithms for uniform machine scheduling with processing set restrictions ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ An optimal online algorithm for fractional scheduling on uniform machines with three hierarchies ⋮ Improved bounds for online scheduling with eligibility constraints ⋮ 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 fractional hierarchical scheduling on uniformly related machines ⋮ Online scheduling with migration on two hierarchical machines ⋮ Optimal online algorithms on two hierarchical machines with tightly-grouped processing times

Cites Work

• Online parallel machines scheduling with two hierarchies
• Online and semi-online scheduling of two machines under a grade of service provision
• The hierarchical model for load balancing on two machines
• Online scheduling on parallel machines with two goS levels
• On-line algorithms for the channel assignment problem in cellular networks.
• On-line scheduling revisited
• New lower and upper bounds for on-line scheduling
• Optimal online algorithms for scheduling on two identical machines under a grade of service
• On-Line Load Balancing in a Hierarchical Server Topology
• Better Bounds for Online Scheduling
• The Competitiveness of On-Line Assignments
• Bounds for Certain Multiprocessing Anomalies

This page was built for publication: Online hierarchical scheduling: an approach using mathematical programming