Online scheduling on two uniform machines subject to eligibility constraints

DOI10.1016/J.TCS.2009.06.032zbMath1171.68004OpenAlexW2089482709MaRDI QIDQ837188

Kangbok Lee, Joseph Y.-T. Leung, Michael L. Pinedo

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.06.032

zbMATH Keywords

competitive ratiouniform machinesonline schedulingeligibility constraintsgrade of service eligibility

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)

Related Items (5)

General parametric scheme for the online uniform machine scheduling problem with two different speeds ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ Fast approximation algorithms for uniform machine scheduling with processing set restrictions ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ Improved bounds for online scheduling with eligibility constraints

Cites Work

• Online and semi-online scheduling of two machines under a grade of service provision
• Online scheduling on two uniform machines to minimize the makespan
• Semi-online scheduling on two uniform processors
• On-Line Load Balancing in a Hierarchical Server Topology
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• The Competitiveness of On-Line Assignments

This page was built for publication: Online scheduling on two uniform machines subject to eligibility constraints