The Power of Amortization on Minimizing Total Completion Time with Explorable Uncertainty
For researchers in online scheduling and explorable uncertainty, this work provides tighter competitive analyses and improved algorithms, though the improvements are incremental over prior work.
This paper improves competitive ratios for online scheduling with explorable uncertainty to minimize total completion time, achieving a deterministic ratio of 2.316513 and a randomized ratio of 2.152271 on a single machine, and extending to multiple machines with ratios approaching 2.77629 and 2.51098 as m increases.
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.