Online hierarchical scheduling: an approach using mathematical programming

DOI10.1016/J.TCS.2009.08.014MaRDI QIDQ621843zbMATH OpenOpenAlexFDO

Authors 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

hierarchyonlinemathematical programmingschedulingcompetitive ratio

Mathematics Subject Classification ID

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

Recommendations

• A Mathematical Programming Approach for Online Hierarchical Scheduling
• Semi-online hierarchical scheduling problems with buffer or rearrangements
• Approximating the optimal algorithm for online scheduling problems via dynamic programming
• On-line scheduling revisited
• Time-hierarchical scheduling. A worst case analysis of a hierarchical approach integrating planning and scheduling in an online problem
• Online scheduling on uniform machines with two hierarchies
• Optimal online algorithms for hierarchical scheduling on three parallel machines
• Online scheduling with migration on two hierarchical machines
• scientific article; zbMATH DE number 1617256
• On-line scheduling with precedence constraints

Cites work

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

Cited in

(19)

• Fast approximation algorithms for uniform machine scheduling with processing set restrictions
• Online scheduling with unit processing times and processing set restrictions
• A Mathematical Programming Approach for Online Hierarchical Scheduling
• Makespan minimization in online scheduling with machine eligibility
• Total completion time minimization in online hierarchical scheduling of unit-size jobs
• Online scheduling with migration on two hierarchical machines
• Two approximation schemes for scheduling on parallel machines under a grade of service provision
• An optimal online algorithm for fractional scheduling on uniform machines with three hierarchies
• Semi-online hierarchical scheduling for \(l_p\)-norm load balancing with buffer or rearrangements
• Semi-Online Hierarchical Scheduling on Two Machines for lp-Norm Load Balancing
• Optimal online algorithms for hierarchical scheduling on three parallel machines
• Makespan minimization in online scheduling with machine eligibility
• Improved bounds for online scheduling with eligibility constraints
• Total completion time minimization scheduling on two hierarchical uniform machines
• Bin stretching with migration on two hierarchical machines
• Online fractional hierarchical scheduling on uniformly related machines
• On the optimality of the LP-based algorithm for online scheduling with GoS eligibility constraints
• A best possible algorithm for an online scheduling problem with deteriorating effect in steel box girder section production
• Optimal online algorithms on two hierarchical machines with tightly-grouped processing times

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q621843)