Online parallel machines scheduling with two hierarchies

DOI10.1016/J.TCS.2009.04.007MaRDI QIDQ837151zbMATHOpenAlexFDO

Authors An Zhang, Yiwei Jiang, Zhiyi Tan

Publication date 10 September 2009

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

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

zbMATH Keywords

onlineschedulingcompetitive ratiohierarchical machines

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Online scheduling on uniform machines with two hierarchies
• Optimal online algorithms for hierarchical scheduling on three parallel machines
• Online hierarchical scheduling on two uniform machines with bounded job sizes
• A note on hierarchical scheduling on two uniform machines
• Online fractional hierarchical scheduling on uniformly related machines

Cites work

• scientific article; zbMATH DE number 4130003 (Why is no real title available?)
• Bounds for Certain Multiprocessing Anomalies
• Improved Bounds for the Online Scheduling Problem
• New lower and upper bounds for on-line scheduling
• On randomized online 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 scheduling on parallel machines with two goS levels
• Optimal online algorithms for scheduling on two identical machines under a grade of service
• Parallel machine scheduling under a grade of service provision
• Parallel machine scheduling with job assignment restrictions
• The Competitiveness of On-Line Assignments
• The hierarchical model for load balancing on two machines

Cited in

(43)

• Online hierarchical service scheduling on two identical machines with release times
• Fast approximation algorithms for uniform machine scheduling with processing set restrictions
• A note on hierarchical scheduling on two uniform machines
• scientific article; zbMATH DE number 4099020 (Why is no real title available?)
• Online and semi-online hierarchical scheduling for load balancing on uniform machines
• Preemptive online algorithms for scheduling on three machines with hierarchies
• Online scheduling with unit processing times and processing set restrictions
• A Mathematical Programming Approach for Online Hierarchical Scheduling
• Online MapReduce processing on two identical parallel machines
• Makespan minimization in online scheduling with machine eligibility
• Online hierarchical scheduling on two uniform machines with bounded job sizes
• Algorithms for hierarchical and semi-partitioned parallel scheduling
• Total completion time minimization in online hierarchical scheduling of unit-size jobs
• Online hierarchical scheduling: an approach using mathematical programming
• Online scheduling with migration on two hierarchical machines
• Optimal online algorithms on two hierarchical machines with resource augmentation
• Two approximation schemes for scheduling on parallel machines under a grade of service provision
• An online algorithm for hierarchical scheduling on two identical machines with rejection
• An optimal online algorithm for fractional scheduling on uniform machines with three hierarchies
• Online early work maximization on three hierarchical machines with a common due date
• Optimal online algorithms for hierarchical scheduling on three parallel machines
• Makespan minimization in online scheduling with machine eligibility
• Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs
• Online scheduling of two job types on a set of multipurpose machines with unit processing times
• Optimal algorithms for semi-online machine covering on two hierarchical machines
• Total completion time minimization scheduling on two hierarchical uniform machines
• On-line booking policies and competitive analysis of medical examination in hospital
• Time-hierarchical scheduling. A worst case analysis of a hierarchical approach integrating planning and scheduling in an online problem
• An asymptotically optimal online algorithm to minimize the total completion time on two multipurpose machines with unit processing times
• Optimal online algorithms on two hierarchical machines with resource augmentation
• On the optimality of the \(TLS\) algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines
• Semi-online algorithms for hierarchical scheduling on three parallel machines with a buffer size of 1
• Bin stretching with migration on two hierarchical machines
• Heuristics for online scheduling on identical parallel machines with two GoS levels
• Online scheduling on two parallel identical machines under a grade of service provision
• Notes on a hierarchical scheduling problem on identical machines
• Semi-online scheduling with two GoS levels and unit processing time
• Online fractional hierarchical scheduling on uniformly related machines
• Parallel machine scheduling with hierarchical and rejection
• On the optimality of the LP-based algorithm for online scheduling with GoS eligibility constraints
• Online scheduling on uniform machines with two hierarchies
• Optimal online algorithms on two hierarchical machines with tightly-grouped processing times
• Parallel machine scheduling with service hierarchy and rejection

This page was built for publication: Online parallel machines scheduling with two hierarchies

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