A 2-competitive largest job on least loaded machine online algorithm based on the multi list scheduling model

DOI10.1007/978-981-16-6890-6_42OpenAlexW4225496743MaRDI QIDQ2079980

Rakesh Mohanty, Debasis Dwibedy

Publication date: 7 October 2022

Full work available at URL: https://doi.org/10.1007/978-981-16-6890-6_42

zbMATH Keywords

competitive analysismakespanonline schedulingidentical machinesmulti listparallel submissions

Mathematics Subject Classification ID

Computer science (68-XX) Operations research, mathematical programming (90-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• A simple semi on-line algorithm for \(\mathrm{P}2//C_{\max}\) with a buffer
• New algorithms for an ancient scheduling problem.
• Semi on-line algorithms for the partition problem
• A better lower bound for on-line scheduling
• Online algorithms: a survey
• On-line scheduling revisited
• Algorithms better than LPT for semi-online scheduling with decreasing processing times
• Semi-online algorithms for parallel machine scheduling problems
• New lower and upper bounds for on-line scheduling
• Semi-online hierarchical scheduling problems with buffer or rearrangements
• Online makespan minimization with parallel schedules
• Online Minimum Makespan Scheduling with a Buffer
• The Power of Reordering for Online Minimum Makespan Scheduling
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• Better Bounds for Online Scheduling
• A Better Algorithm for an Ancient Scheduling Problem
• Reducibility among Combinatorial Problems
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Semi-online scheduling with decreasing job sizes