The Power of Amortization on Scheduling with Explorable Uncertainty

Liu, Alison Hsiang-Hsuan ORCID: 0000-0002-0194-9360, Liu, Fu-Hong ORCID: 0000-0001-6073-8179, Wong, Prudence WH ORCID: 0000-0001-7935-7245 and Zhang, Xiao-Ou (2023) The Power of Amortization on Scheduling with Explorable Uncertainty. In: Workshop on Approximation and Online Algorithms (WAOA), 2023-9-7 - 2023-9-8, Amsterdam, the Netherlands.

PDF
main.pdf - Other
Download (1MB) | Preview

Official URL: http://dx.doi.org/10.1007/978-3-031-49815-2_7

Abstract

In this work, we study a scheduling problem with explorable uncertainty. 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 on a single machine with a minimum total completion time. The challenge lies in deciding which jobs to test and the order of testing/processing jobs. The online problem was first introduced with unit testing time [5, 6] and later generalized to variable testing times [1]. For this general setting, the upper bounds of the competitive ratio are shown to be 4 and 3.3794 for deterministic and randomized online algorithms [1]; while the lower bounds for unit testing time stands [5, 6], which are 1.8546 (deterministic) and 1.6257 (randomized). We continue the study on variable testing times setting. We first enhance the analysis framework in [1] and improve the competitive ratio of the deterministic algorithm in [1] from 4 to. 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.

Item Type:	Conference or Workshop Item (Unspecified)
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	28 Sep 2023 09:28
Last Modified:	06 Jan 2024 23:24
DOI:	10.1007/978-3-031-49815-2_7
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3173142