Online Flexible Busy Time Scheduling on Heterogeneous Machines
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918373326061568 |
|---|---|
| author | Calinescu, Gruia Davies, Sami Khuller, Samir Zhang, Shirley |
| author_facet | Calinescu, Gruia Davies, Sami Khuller, Samir Zhang, Shirley |
| contents | We study the online busy time scheduling model on heterogeneous machines. In our setting, jobs with uniform length arrive online with a deadline that becomes known to the algorithm at the job's arrival time. An algorithm has access to machines, each with different associated capacities and costs. The goal is to schedule jobs on machines by their deadline, so that the total cost incurred by the scheduling algorithm is minimized. While busy time scheduling has been well-studied, relatively little is known when machines are heterogeneous (i.e., have different costs and capacities), despite this natural theoretical generalization being the most practical model for clients using cloud computing services. We make significant progress in understanding this model by designing an 8-competitive algorithm for the problem on unit-length jobs and providing a lower bound of 2 on the competitive ratio. The lower bound is tight in the setting when jobs form non-nested intervals. Our 8-competitive algorithm generalizes to one with competitive ratio $8(2p-1)/p < 16$ when all jobs have uniform length $p$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_11109 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Online Flexible Busy Time Scheduling on Heterogeneous Machines Calinescu, Gruia Davies, Sami Khuller, Samir Zhang, Shirley Data Structures and Algorithms We study the online busy time scheduling model on heterogeneous machines. In our setting, jobs with uniform length arrive online with a deadline that becomes known to the algorithm at the job's arrival time. An algorithm has access to machines, each with different associated capacities and costs. The goal is to schedule jobs on machines by their deadline, so that the total cost incurred by the scheduling algorithm is minimized. While busy time scheduling has been well-studied, relatively little is known when machines are heterogeneous (i.e., have different costs and capacities), despite this natural theoretical generalization being the most practical model for clients using cloud computing services. We make significant progress in understanding this model by designing an 8-competitive algorithm for the problem on unit-length jobs and providing a lower bound of 2 on the competitive ratio. The lower bound is tight in the setting when jobs form non-nested intervals. Our 8-competitive algorithm generalizes to one with competitive ratio $8(2p-1)/p < 16$ when all jobs have uniform length $p$. |
| title | Online Flexible Busy Time Scheduling on Heterogeneous Machines |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.11109 |