Breaking 1 - 1/e Barrier for Nonpreemptive Throughput Maximization

DOI10.1137/17M1148438zbMath1450.90004OpenAlexW4244842914MaRDI QIDQ5130573

Shi Li, Sungjin Im, Benjamin Moseley

Publication date: 28 October 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

schedulingapproximationlinear programthroughputroundingnonpreemptive

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items

Online Throughput Maximization on Unrelated Machines: Commitment is No Burden

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An O\((n^4)\) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
• Maximizing the value of a space mission
• On the approximability of an interval scheduling problem
• Scheduling time-constrained communication in linear networks
• Approximating the Throughput of Multiple Machines in Real-Time Scheduling
• Improvements in throughout maximization for real-time scheduling
• The Fixed Job Schedule Problem with Spread-Time Constraints
• Two-Processor Scheduling with Start-Times and Deadlines
• $\text{D}^{\textit{over}}$: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems
• Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems