2022/10/11 by Leah Epstein, Epstein, Leah
Computer Science · Engineering · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #Optimization and Search Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2210.05543
openalex publication_date 2022/10/11 · openalex created_date 2022/10/14 · openalex updated_date 2026/07/28
We consider online preemptive scheduling of jobs arriving one by one, to be assigned to two identical machines, with the goal of makespan minimization. We study the effect of selecting the best solution out of two independent solutions constructed in parallel in an online fashion. Two cases are analyzed, where one case is purely online, and in the other one jobs are presented sorted by non-increasing sizes. We show that using two solutions rather than one improves the performance significantly, but that an optimal solution cannot be obtained for any constant number of solutions constructed in parallel. Our algorithms have the best possible competitive ratios out of algorithms for each one of the classes.