Online Non-Preemptive Scheduling to Optimize Max Stretch on a Single Machine

Abstract : We consider in this work a classical online scheduling problem with release times on a single machine. The quality of service of a job is measured by its stretch, which is defined as the ratio of its response time over its processing time. Our objective is to schedule the jobs non-preemptively in order to optimize the maximum stretch. We present both positive and negative theoretical results. First, we provide an online algorithm based on a waiting strategy which is (1 + √ 5−1 2 ∆)-competitive where ∆ is the upper bound on the ratio of processing times of any two jobs. Then, we show that no online algorithm has a competitive ratio better than 1 + √ 5−1 2 ∆. The proposed algorithm is asymptotically the best algorithm for optimizing the maximum stretch on a single machine.
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download
Contributor : Abhinav Srivastav <>
Submitted on : Monday, May 16, 2016 - 4:53:39 PM
Last modification on : Wednesday, August 21, 2019 - 10:22:04 AM
Long-term archiving on : Wednesday, November 16, 2016 - 5:34:04 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License


  • HAL Id : hal-01309052, version 2


Pierre-Francois Dutot, Erik Saule, Abhinav Srivastav, Denis Trystram. Online Non-Preemptive Scheduling to Optimize Max Stretch on a Single Machine. 22nd International Computing and Combinatorics Conference (COCOON 2016), Aug 2016, Ho-Chi-Minh-Ville, Vietnam. ⟨hal-01309052v2⟩



Record views


Files downloads