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_42MaRDI QIDQ2079980zbMATH OpenOpenAlexFDO

Authors Debasis Dwibedy, Rakesh Mohanty

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)

Recommendations

• On the optimality of the \(TLS\) algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines
• Online scheduling of parallel jobs on two machines is 2-competitive
• On the optimality of list scheduling for online uniform machines scheduling
• A best possible online algorithm for scheduling equal-length jobs on two machines with chain precedence constraints
• A \(2.28\)-competitive algorithm for online scheduling on identical machines
• A best online algorithm for scheduling on two parallel batch machines
• An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time
• A modified list scheduling algorithm for the online hierarchical load balancing problem with bounded processing times
• Online scheduling of two job types on a set of multipurpose machines with unit processing times
• scientific article; zbMATH DE number 6490206

Cites work

• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• A Better Algorithm for an Ancient Scheduling Problem
• A better lower bound for on-line scheduling
• A simple semi on-line algorithm for \(\mathrm{P}2//C_{\max}\) with a buffer
• Algorithms better than LPT for semi-online scheduling with decreasing processing times
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• Better Bounds for Online Scheduling
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• New algorithms for an ancient scheduling problem.
• New lower and upper bounds for on-line scheduling
• On-line scheduling revisited
• Online algorithms: a survey
• Online minimum makespan scheduling with a buffer
• Reducibility among combinatorial problems
• Semi on-line algorithms for the partition problem
• Semi-online algorithms for parallel machine scheduling problems
• Semi-online hierarchical scheduling problems with buffer or rearrangements
• Semi-online scheduling with decreasing job sizes
• The Power of Reordering for Online Minimum Makespan Scheduling

This page was built for publication: A 2-competitive largest job on least loaded machine online algorithm based on the multi list scheduling model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2079980)