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
Contributor : Abhinav Srivastav <>
Submitted on : Thursday, April 28, 2016 - 6:24:20 PM
Last modification on : Wednesday, August 21, 2019 - 10:22:04 AM
Long-term archiving on : Tuesday, November 15, 2016 - 5:25:40 PM


Files produced by the author(s)


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


  • HAL Id : hal-01309052, version 1


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, Aug 2016, Ho Chi Minh City, Vietnam. ⟨hal-01309052v1⟩



Record views


Files downloads