Scheduling with Obligatory Tests
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_ | 1866909230345224192 |
|---|---|
| author | Dogeas, Konstantinos Erlebach, Thomas Liang, Ya-Chun |
| author_facet | Dogeas, Konstantinos Erlebach, Thomas Liang, Ya-Chun |
| contents | Motivated by settings such as medical treatments or aircraft maintenance, we consider a scheduling problem with jobs that consist of two operations, a test and a processing part. The time required to execute the test is known in advance while the time required to execute the processing part becomes known only upon completion of the test. We use competitive analysis to study algorithms for minimizing the sum of completion times for $n$ given jobs on a single machine. As our main result, we prove using a novel analysis technique that the natural $1$-SORT algorithm has competitive ratio at most 1.861. For the special case of uniform test times, we show that a simple threshold-based algorithm has competitive ratio at most 1.585. We also prove a lower bound that shows that no deterministic algorithm can be better than $\sqrt{2}$-competitive even in the case of uniform test times. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_16734 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Scheduling with Obligatory Tests Dogeas, Konstantinos Erlebach, Thomas Liang, Ya-Chun Data Structures and Algorithms F.2.2 Motivated by settings such as medical treatments or aircraft maintenance, we consider a scheduling problem with jobs that consist of two operations, a test and a processing part. The time required to execute the test is known in advance while the time required to execute the processing part becomes known only upon completion of the test. We use competitive analysis to study algorithms for minimizing the sum of completion times for $n$ given jobs on a single machine. As our main result, we prove using a novel analysis technique that the natural $1$-SORT algorithm has competitive ratio at most 1.861. For the special case of uniform test times, we show that a simple threshold-based algorithm has competitive ratio at most 1.585. We also prove a lower bound that shows that no deterministic algorithm can be better than $\sqrt{2}$-competitive even in the case of uniform test times. |
| title | Scheduling with Obligatory Tests |
| topic | Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2406.16734 |