Approximation schemes for scheduling on uniformly related and identical parallel machines

DOI10.1007/S00453-003-1077-7MaRDI QIDQ1879359zbMATH OpenOpenAlexFDO

Authors Leah Epstein, Jiří Sgall

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

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Recommendations

• Publication:4938775
• Approximation schemes for scheduling on parallel machines
• Improved approximation schemes for scheduling unrelated parallel machines
• Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
• Approximation algorithms for scheduling unrelated parallel machines

Cited in

(36)

• Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines
• Performance guarantees of jump neighborhoods on restricted related parallel machines
• Polynomial-time approximation schemes for a class of integrated network design and scheduling problems with parallel identical machines
• A unified view of parallel machine scheduling with interdependent processing rates
• Approximation for scheduling on uniform nonsimultaneous parallel machines
• Scheduling with bully selfish jobs
• Approximation algorithms for job scheduling with block-type conflict graphs
• Performance guarantees of local search for minsum scheduling problems
• Online C-benevolent job scheduling on multiple machines
• Tighter approximation bounds for LPT scheduling in two special cases
• Performance guarantee of the jump neighborhood for scheduling jobs on uniformly related machines
• Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints
• An efficient polynomial time approximation scheme for load balancing on uniformly related machines
• Online scheduling with machine cost and rejection
• Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms
• Approximating Real-Time Scheduling on Identical Machines
• Bag-Of-Tasks Scheduling on Related Machines
• Scheduling with uncertain processing times in mixed-criticality systems
• A unified approach to truthful scheduling on related machines
• New approximation bounds for LPT scheduling
• Semi-online machine covering for two uniform machines
• scientific article; zbMATH DE number 1405790 (Why is no real title available?)
• Approximate separable multichoice optimization over monotone systems
• Scheduling with machine cost and rejection
• EPTAS for load balancing problem on parallel machines with a non-renewable resource
• Online scheduling with rejection and reordering: exact algorithms for unit size jobs
• Approximations and auctions for scheduling batches on related machines
• A unified framework for designing EPTAS for load balancing on parallel machines
• Approximation Algorithms For Scheduling On Uniform Processors
• Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
• Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs
• An approximation algorithm for identical parallel machine scheduling with resource dependent processing times
• New algorithmic results for bin packing and scheduling
• Semi-online scheduling on two identical machines with rejection
• A truthful constant approximation for maximizing the minimum load on related machines
• Optimal semi-online algorithm 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

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