The Power of Amortization on Scheduling with Explorable Uncertainty

Alison Liu*, Fu-Hong Liu, Prudence W.H. Wong, Xiao-Ou Zhang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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.
Original languageEnglish
Title of host publicationApproximation and Online Algorithms
PublisherSpringer
Number of pages14
ISBN (Electronic)978-3-031-49815-2
ISBN (Print)978-3-031-49814-5
DOIs
Publication statusPublished - 22 Dec 2023

Fingerprint

Dive into the research topics of 'The Power of Amortization on Scheduling with Explorable Uncertainty'. Together they form a unique fingerprint.

Cite this