Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9655161 | Discrete Applied Mathematics | 2005 | 20 Pages |
Abstract
This paper investigates the semi-online version of scheduling problem P||Cmax on a three-machine system. We assume that all jobs have their processing times between p and rp (p>0,r⩾1). We give a comprehensive competitive ratio of LS algorithm which is a piecewise function on r⩾1. It shows that LS is an optimal semi-online algorithm for every râ[1,1.5], [3,2] and [6,+â). We further present an optimal algorithm for every râ[2,2.5], and an almost optimal algorithm for every râ(2.5,3] where the largest gap between its competitive ratio and the lower bound of the problem is at most 0.01417. We also present an improved algorithm with smaller competitive ratio than that of LS for every râ(3,6).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yong He, György Dósa,