Approximation schemes for scheduling on uniformly related and identical parallel machines
From MaRDI portal
Publication:1879359
DOI10.1007/s00453-003-1077-7zbMath1072.90013OpenAlexW2619122734MaRDI QIDQ1879359
Publication date: 22 September 2004
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-003-1077-7
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)
Related Items (25)
New Algorithmic Results for Bin Packing and Scheduling ⋮ New approximation bounds for LPT scheduling ⋮ Scheduling with machine cost and rejection ⋮ Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms ⋮ Approximations and auctions for scheduling batches on related machines ⋮ Semi-online scheduling on two identical machines with rejection ⋮ A truthful constant approximation for maximizing the minimum load on related machines ⋮ A unified framework for designing EPTAS for load balancing on parallel machines ⋮ Approximate separable multichoice optimization over monotone systems ⋮ Optimal semi-online algorithm for scheduling with rejection on two uniform machines ⋮ An efficient polynomial time approximation scheme for load balancing on uniformly related machines ⋮ Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints ⋮ Online scheduling with rejection and reordering: exact algorithms for unit size jobs ⋮ Online scheduling with machine cost and rejection ⋮ Online C-benevolent job scheduling on multiple machines ⋮ Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs ⋮ Scheduling with bully selfish jobs ⋮ EPTAS for load balancing problem on parallel machines with a non-renewable resource ⋮ A unified view of parallel machine scheduling with interdependent processing rates ⋮ A Unified Approach to Truthful Scheduling on Related Machines ⋮ Tighter approximation bounds for LPT scheduling in two special cases ⋮ Scheduling with uncertain processing times in mixed-criticality systems ⋮ Semi-online machine covering for two uniform machines ⋮ Performance guarantees of local search for minsum scheduling problems ⋮ Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines
This page was built for publication: Approximation schemes for scheduling on uniformly related and identical parallel machines
