Tight lower bounds for semi-online scheduling on two uniform machines with known optimum

• Published in: Central European journal of operations research 2019-12, Vol.27 (4), p.1107-1130
• Main Authors: Dósa, György, Fügenschuh, Armin, Tan, Zhiyi, Tuza, Zsolt, Węsek, Krzysztof
• Format: Article
• Language: English
• Subjects: Algorithms; Business and Management; Lower bounds; Machinery; Magneto-electric machines; Mathematical optimization; Methods; Operations research; Operations Research/Decision Theory; Optimization; Original Paper; Production scheduling; Scheduling; Scheduling (Management); Scheduling algorithms
• ISSN: 1435-246X; 1613-9178
• DOI: 10.1007/s10100-018-0536-9

This problem is about scheduling a number of jobs 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. 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 [ 1 + 21 4 , 3 + 73 8 ] ≈ [ 1.3956 , 1.443 ] and [ 5 3 , 4 + 133 9 ] ≈ [ 5 3 , 1.7258 ] , except a very narrow interval.