Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.13357 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909026120368128 |
|---|---|
| author | Krekelberg, Bob Liu, Alison Hsiang-Hsuan Liu, Fu-Hong Wong, Prudence W. H. Zhang, Xiao-Ou |
| author_facet | Krekelberg, Bob Liu, Alison Hsiang-Hsuan Liu, Fu-Hong Wong, Prudence W. H. Zhang, Xiao-Ou |
| contents | We study online scheduling to minimize total completion time with explorable uncertainty on single and multiple machines. Each job comes with an upper limit of its processing time, which could be potentially reduced by testing the job, which also takes time. The objective is to schedule all jobs with minimum total completion time. The challenge lies in deciding which jobs to test, the order of testing/processing jobs, and in multiple machine case which machine a job is allocated to. In multiple machine case, testing and processing of a job are allowed to be scheduled on different machines.
Different settings have been studied before. In this work, we first consider the variable testing times setting. We enhance the analysis framework in Albers and Eckl (2020) and improve the analysis of the competitive ratio of their deterministic single machine algorithm from $4$ to $1+\sqrt{2} \approx 2.4143$. Using the new analysis framework, we propose a new deterministic algorithm that further improves the competitive ratio to $2.316513$. The new framework also enables us to develop a randomized algorithm improving the expected competitive ratio from $3.3794$ to $2.152271$. We further show that with $m$~machines, by extending the framework of Gong et al. (2024), there exists a deterministic $2.77629-(0.45977/m)$-competitive algorithm and a randomized $2.51098-(0.3587/m)$-competitive algorithm. The performance of the algorithms on multiple machines when $m = 1$ matches the current best algorithms on a single machine for variable testing times shown in this paper. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_13357 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Power of Amortization on Minimizing Total Completion Time with Explorable Uncertainty Krekelberg, Bob Liu, Alison Hsiang-Hsuan Liu, Fu-Hong Wong, Prudence W. H. Zhang, Xiao-Ou Discrete Mathematics We study online scheduling to minimize total completion time with explorable uncertainty on single and multiple machines. Each job comes with an upper limit of its processing time, which could be potentially reduced by testing the job, which also takes time. The objective is to schedule all jobs with minimum total completion time. The challenge lies in deciding which jobs to test, the order of testing/processing jobs, and in multiple machine case which machine a job is allocated to. In multiple machine case, testing and processing of a job are allowed to be scheduled on different machines. Different settings have been studied before. In this work, we first consider the variable testing times setting. We enhance the analysis framework in Albers and Eckl (2020) and improve the analysis of the competitive ratio of their deterministic single machine algorithm from $4$ to $1+\sqrt{2} \approx 2.4143$. Using the new analysis framework, we propose a new deterministic algorithm that further improves the competitive ratio to $2.316513$. The new framework also enables us to develop a randomized algorithm improving the expected competitive ratio from $3.3794$ to $2.152271$. We further show that with $m$~machines, by extending the framework of Gong et al. (2024), there exists a deterministic $2.77629-(0.45977/m)$-competitive algorithm and a randomized $2.51098-(0.3587/m)$-competitive algorithm. The performance of the algorithms on multiple machines when $m = 1$ matches the current best algorithms on a single machine for variable testing times shown in this paper. |
| title | The Power of Amortization on Minimizing Total Completion Time with Explorable Uncertainty |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2503.13357 |