Competitive Kill-and-Restart and Preemptive Strategies for Non-Clairvoyant Scheduling
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916332033802240 |
|---|---|
| author | Jäger, Sven Sagnol, Guillaume Waldschmidt, Daniel Schmidt genannt Warode, Philipp |
| author_facet | Jäger, Sven Sagnol, Guillaume Waldschmidt, Daniel Schmidt genannt Warode, Philipp |
| contents | We study kill-and-restart and preemptive strategies for the fundamental scheduling problem of minimizing the sum of weighted completion times on a single machine in the non-clairvoyant setting. First, we show a lower bound of~$3$ for any deterministic non-clairvoyant kill-and-restart strategy. Then, we give for any $b > 1$ a tight analysis for the natural $b$-scaling kill-and-restart strategy as well as for a randomized variant of it. In particular, we show a competitive ratio of $(1+3\sqrt{3})\approx 6.197$ for the deterministic and of $\approx 3.032$ for the randomized strategy, by making use of the largest eigenvalue of a Toeplitz matrix. In addition, we show that the preemptive Weighted Shortest Elapsed Time First (WSETF) rule is $2$-competitive when jobs are released online, matching the lower bound for the unit weight case with trivial release dates for any non-clairvoyant algorithm. Using this result as well as the competitiveness of round-robin for multiple machines, we prove performance guarantees smaller than $10$ for adaptions of the $b$-scaling strategy to online release dates and unweighted jobs on identical parallel machines. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_02044 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Competitive Kill-and-Restart and Preemptive Strategies for Non-Clairvoyant Scheduling Jäger, Sven Sagnol, Guillaume Waldschmidt, Daniel Schmidt genannt Warode, Philipp Data Structures and Algorithms We study kill-and-restart and preemptive strategies for the fundamental scheduling problem of minimizing the sum of weighted completion times on a single machine in the non-clairvoyant setting. First, we show a lower bound of~$3$ for any deterministic non-clairvoyant kill-and-restart strategy. Then, we give for any $b > 1$ a tight analysis for the natural $b$-scaling kill-and-restart strategy as well as for a randomized variant of it. In particular, we show a competitive ratio of $(1+3\sqrt{3})\approx 6.197$ for the deterministic and of $\approx 3.032$ for the randomized strategy, by making use of the largest eigenvalue of a Toeplitz matrix. In addition, we show that the preemptive Weighted Shortest Elapsed Time First (WSETF) rule is $2$-competitive when jobs are released online, matching the lower bound for the unit weight case with trivial release dates for any non-clairvoyant algorithm. Using this result as well as the competitiveness of round-robin for multiple machines, we prove performance guarantees smaller than $10$ for adaptions of the $b$-scaling strategy to online release dates and unweighted jobs on identical parallel machines. |
| title | Competitive Kill-and-Restart and Preemptive Strategies for Non-Clairvoyant Scheduling |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2211.02044 |