- Semi-Online Scheduling on Two Uniform Machines with Known Optimum, Part I: Tight Lower Bounds György Dósa(dosagyalmos.vein.hu) Armin Fügenschuh(fuegenschuhhsu-hh.de) Zhiyi Tan(tanzyzju.edu.cn) Zsolt Tuza(tuzadcs.uni-pannon.hu) Krzysztof Wesek(wesekkhsu-hh.de) Abstract: This problem is about to schedule a number of jobs of different lengths on two uniform machines with given speeds $1$ and $s \geq 1$, so that the overall completion 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 arrive one after the other, while the scheduling algorithm knows the optimum value of the corresponding offline problem. One can ask how close any possible 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. We contribute to this question by constructing tight lower bounds for all values of $s$ in the intervals $[\frac{1+\sqrt{21}}{4},\frac{3+\sqrt{73}}{8}]\approx\lbrack1.3956,1.443]$ and $[\frac{5}{3},\frac{4+\sqrt{133}}{9}]\approx\lbrack\frac{5}{3},1.7258]$, except a very narrow interval, approximately $[1.6934,1.6963]$, where our new lower bound is "almost tight". A novel feature of the (rather complicated) construction of malicious input sequences is that our method goes several levels deeper than the earlier ones in the literature. Keywords: Semi-online scheduling, makespan minimization, machine scheduling, lower bound. Category 1: Combinatorial Optimization (Approximation Algorithms ) Citation: Angewandte Mathematik und Optimierung Schriftenreihe / Applied Mathematics and Optimization Series AMOS#27(2015), Helmut Schmidt University / University of the Federal Armed Forces Hamburg, Germany Download: [PDF]Entry Submitted: 08/04/2015Entry Accepted: 08/28/2015Entry Last Modified: 08/04/2015Modify/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 Optimization Online is supported by the Mathematical Optmization Society.