Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs

DOI10.1080/00207160.2014.922682zbMath1314.90035OpenAlexW2038536406MaRDI QIDQ5248073

He Jiang, Ning Ding, Xin Han, Xin Chen, György Dósa

Publication date: 27 April 2015

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207160.2014.922682

zbMATH Keywords

competitive ratioscheduling problemsemi-onlinehierarchical constraint

Mathematics Subject Classification ID

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)

Related Items (5)

Semi-online early work maximization problem on two hierarchical machines with partial information of processing time ⋮ Semi-online scheduling: a survey ⋮ Bin stretching with migration on two hierarchical machines ⋮ Online early work maximization problem on two hierarchical machines with buffer or rearrangements ⋮ Semi-online Machine Covering on Two Hierarchical Machines with Known Total Size of Low-Hierarchy Jobs

Cites Work

• A simple semi on-line algorithm for \(\mathrm{P}2//C_{\max}\) with a buffer
• Semi-online scheduling problems on a small number of machines
• A note on hierarchical scheduling on two uniform machines
• Improved bounds for online scheduling with 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
• An FPTAS for parallel-machine scheduling under a grade of service provision to minimize makespan
• A comment on parallel-machine scheduling under a grade of service provision to minimize makespan
• Semi on-line algorithms for the partition problem
• Bin stretching revisited
• Semi-on-line problems on two identical machines with combined partial information
• Parallel machine scheduling under a grade of service provision
• A note on on-line scheduling with partial information
• Semi-online hierarchical scheduling problems with buffer or rearrangements
• Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines
• Optimal online algorithms for scheduling on two identical machines under a grade of service
• On-Line Load Balancing in a Hierarchical Server Topology
• Optimal Semi-online Scheduling Algorithms on Two Parallel Identical Machines under a Grade of Service Provision
• Bounds for Certain Multiprocessing Anomalies
• Makespan minimization in online scheduling with machine eligibility

This page was built for publication: Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs