A Competitive Algorithm for Throughput Maximization on Identical Machines
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914920997584896 |
|---|---|
| author | Moseley, Benjamin Pruhs, Kirk Stein, Clifford Zhou, Rudy |
| author_facet | Moseley, Benjamin Pruhs, Kirk Stein, Clifford Zhou, Rudy |
| contents | This paper considers the basic problem of scheduling jobs online with preemption to maximize the number of jobs completed by their deadline on $m$ identical machines. The main result is an $O(1)$ competitive deterministic algorithm for any number of machines $m >1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_06564 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | A Competitive Algorithm for Throughput Maximization on Identical Machines Moseley, Benjamin Pruhs, Kirk Stein, Clifford Zhou, Rudy Data Structures and Algorithms This paper considers the basic problem of scheduling jobs online with preemption to maximize the number of jobs completed by their deadline on $m$ identical machines. The main result is an $O(1)$ competitive deterministic algorithm for any number of machines $m >1$. |
| title | A Competitive Algorithm for Throughput Maximization on Identical Machines |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2111.06564 |