Approximating the Throughput of Multiple Machines in Real-Time Scheduling

DOI10.1137/S0097539799354138zbMath0994.68073OpenAlexW2069832779MaRDI QIDQ2784456

Baruch Schieber, Joseph (Seffi) Naor, Sudipto Guha, Amotz Bar-Noy

Publication date: 23 April 2002

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

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

zbMATH Keywords

schedulingapproximation algorithmsthroughputreal-time schedulingparallel machines schedulingmultiple machines scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Communication networks in operations research (90B18) Approximation algorithms (68W25)

Related Items (40)

Improved algorithms for resource allocation under varying capacity ⋮ Graph colouring approaches for a satellite range scheduling problem ⋮ Anarchy in the UJ: coordination mechanisms for minimizing the number of late jobs ⋮ Fast primal-dual distributed algorithms for scheduling and matching problems ⋮ Resource loading with time windows ⋮ Analysis of bounds for a capacitated single-item lot-sizing problem ⋮ High-performance technique for satellite range scheduling ⋮ Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ Inverse interval scheduling via reduction on a single machine ⋮ On Lagrangian relaxation for constrained maximization and reoptimization problems ⋮ A branch-and-price algorithm to solve the molten iron allocation problem in iron and steel industry ⋮ Minimizing the number of tardy jobs in two-machine settings with common due date ⋮ The quality of equilibria for set packing and throughput scheduling games ⋮ A truthful mechanism for value-based scheduling in cloud computing ⋮ Online Throughput Maximization on Unrelated Machines: Commitment is No Burden ⋮ Coordinated scheduling of production and delivery with production window and delivery capacity constraints ⋮ Unnamed Item ⋮ Breaking 1 - 1/e Barrier for Nonpreemptive Throughput Maximization ⋮ Scheduling split intervals with non-uniform demands ⋮ Bicriteria scheduling for contiguous and non contiguous parallel tasks ⋮ Bandwidth allocation in cellular networks with multiple interferences ⋮ Online C-benevolent job scheduling on multiple machines ⋮ AFSCN scheduling: how the problem and solution have evolved ⋮ Maximizing Throughput in Flow Shop Real-Time Scheduling ⋮ Grasp and delivery for moving objects on broken lines ⋮ Integrated production and delivery scheduling with disjoint windows ⋮ Randomized priority algorithms ⋮ Approximation algorithms for variable voltage processors: min energy, max throughput and online heuristics ⋮ Conversion of coloring algorithms into maximum weight independent set algorithms ⋮ On Lagrangian Relaxation and Subset Selection Problems ⋮ Throughput scheduling with equal additive laxity ⋮ Cost-sharing games in real-time scheduling systems ⋮ Throughput scheduling with equal additive laxity ⋮ Cost-sharing games in real-time scheduling systems ⋮ Bandwidth-constrained allocation in grid computing ⋮ Priority algorithms for the subset-sum problem ⋮ Approximation Algorithms for Variable Voltage Processors: Min Energy, Max Throughput and Online Heuristics ⋮ Fair and efficient cake division with connected pieces ⋮ On the Price of Anarchy of cost-sharing in real-time scheduling systems ⋮ Primal-dual approximation algorithms for a packing-covering pair of problems

This page was built for publication: Approximating the Throughput of Multiple Machines in Real-Time Scheduling