  


New Lower Bounds for Semionline Scheduling on Two Uniform Machines with Known Optimum
György Dósa(dosagyalmos.vein.hu) Abstract: This problem is about to schedule a number of jobs of different lengths on two uniform machines with given speeds 1 and s ≥ 1, so that the overall finishing time, i.e. the makespan, is earliest possible. We consider a semi online variant introduced (for equal speeds) by Azar and Regev, where the jobs are arriving one after the other, while the scheduling algorithm knows the optimum value of the corresponding offline problem. It is desired to construct an algorithm that achieves a schedule close to this optimum value for any given sequence of incoming jobs. Furthermore, one can ask how close any potential algorithm could get to the optimum value, that is, to give a lower bound on the competitive ratio: the supremum over ratios between the value of the solution given by the algorithm and the optimal offline solution. For certain values of s, there are already algorithms known to be tight in the sense that they are scheduling not worse than this bound. For other values of s, this question remained open. We contribute to this question by constructing better lower bounds for some values of s. As a consequence, this proves that the two algorithms given by Ng et al. were in fact optimal, at least, for certain intervals of s. Keywords: Semionline scheduling, makespan minimization, machine scheduling, lower bounds Category 1: Applications  OR and Management Sciences (Scheduling ) Citation: Applied Mathematics and Optimization Series AMOS#20 (2015), Helmut Schmidt University / University of the Federal Armed Forces Hamburg, Holstenhofweg 85, 22043 Hamburg, Germany Download: [PDF] Entry Submitted: 01/10/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  