A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling

DOI10.1137/S0097539798348110zbMath0992.68009OpenAlexW1966275651MaRDI QIDQ2719127

Antonio Miranda, Jian'er Chen

Publication date: 21 June 2001

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539798348110

zbMATH Keywords

approximation algorithmjob schedulingpolynomial time approximation schememultiprocessor processing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Dynamic programming (90C39) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (7)

A simple linear time approximation algorithm for multi-processor job scheduling on four processors ⋮ Polynomial time approximation schemes and parameterized complexity ⋮ On the complexity of adjacent resource scheduling ⋮ Product warranty logistics: issues and challenges. ⋮ Confronting intractability via parameters ⋮ Grouping techniques for scheduling problems: simpler and faster ⋮ Parallel machine scheduling with speed-up resources

This page was built for publication: A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling