Tighter Bounds on Non-clairvoyant Parallel Machine Scheduling with Prediction to Minimize Makespan
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916691293765632 |
|---|---|
| author | Chen, Tianqi Tan, Zhiyi |
| author_facet | Chen, Tianqi Tan, Zhiyi |
| contents | This paper investigates the non-clairvoyant parallel machine scheduling problem with prediction, with the objective of minimizing the makespan. Improved lower bounds for the problem and competitive ratios of online algorithms with respect to the prediction error are presented for both the non-preemptive and preemptive cases on m identical machines. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_10945 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tighter Bounds on Non-clairvoyant Parallel Machine Scheduling with Prediction to Minimize Makespan Chen, Tianqi Tan, Zhiyi Data Structures and Algorithms This paper investigates the non-clairvoyant parallel machine scheduling problem with prediction, with the objective of minimizing the makespan. Improved lower bounds for the problem and competitive ratios of online algorithms with respect to the prediction error are presented for both the non-preemptive and preemptive cases on m identical machines. |
| title | Tighter Bounds on Non-clairvoyant Parallel Machine Scheduling with Prediction to Minimize Makespan |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.10945 |