Online Throughput Maximization on Unrelated Machines: Commitment is No Burden

DOI10.1145/3569582arXiv1912.10769OpenAlexW3216068169MaRDI QIDQ6075745

Nicole Megow, Franziska Eberle, Kevin Schewior

Publication date: 23 October 2023

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1912.10769

zbMATH Keywords

migrationcompetitive analysisonline algorithmsthroughputunrelated machinesdeadline scheduling

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Competitive algorithms for due date scheduling
• Minimizing the number of late jobs on unrelated machines
• A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
• On the competitiveness of on-line real-time task scheduling
• MOCA: A multiprocessor on-line competitive algorithm for real-time system scheduling
• A competitive algorithm for throughput maximization on identical machines
• Scheduling parallelizable jobs online to maximize throughput
• Approximation schemes for a class of subset selection problems
• Breaking \(1-1/e\) barrier for non-preemptive throughput maximization
• Patience is a virtue: the effect of slack on competitiveness for admission control
• Admission control with immediate notification
• Eliminating Migration in Multi-processor Scheduling
• Approximating the Throughput of Multiple Machines in Real-Time Scheduling
• Improvements in throughout maximization for real-time scheduling
• How to Schedule When You Have to Buy Your Energy
• Speed is as powerful as clairvoyance
• The Power of Migration for Online Slack Scheduling.
• Maximizing job completions online
• $\text{D}^{\textit{over}}$: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems
• Breaking 1 - 1/e Barrier for Nonpreemptive Throughput Maximization
• Complexity of preemptive minsum scheduling on unrelated parallel machines
• Optimally Handling Commitment Issues in Online Throughput Maximization
• A general framework for handling commitment in online throughput maximization

This page was built for publication: Online Throughput Maximization on Unrelated Machines: Commitment is No Burden