Parallel solutions for preemptive makespan scheduling on two identical machines

DOI10.1007/s10951-022-00764-4zbMath1517.90043arXiv2210.05543OpenAlexW4307518093MaRDI QIDQ6102847

Leah Epstein

Publication date: 23 June 2023

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2210.05543

zbMATH Keywords

competitive ratiopreemptive schedulingparallel solutionsjobs arriving over a list

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (1)

Parallel solutions for ordinal scheduling with a small number of machines

Cites Work

• Unnamed Item
• A lower bound for randomized on-line multiprocessor scheduling
• Lower bounds for online makespan minimization on a small number of related machines
• Semi-online scheduling revisited
• Robust algorithms for preemptive scheduling
• Online algorithms with advice for bin packing and scheduling problems
• Online algorithms with advice: the tape model
• Semi-online preemptive scheduling: one algorithm for all variants
• Optimal algorithms for online scheduling with bounded rearrangement at the end
• Weighted online problems with advice
• An efficient algorithm for semi-online multiprocessor scheduling with given total processing time
• Preemptive online scheduling: Optimal algorithms for all speeds
• Optimal and online preemptive scheduling on uniformly related machines
• Semi on-line algorithms for the partition problem
• Bin stretching revisited
• On-line scheduling revisited
• Algorithms better than LPT for semi-online scheduling with decreasing processing times
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• An optimal algorithm for preemptive on-line scheduling
• Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes
• Parallel online algorithms for the Bin Packing Problem
• Online makespan minimization with parallel schedules
• New approximation bounds for LPT scheduling
• On the value of job migration in online makespan minimization
• An efficient algorithm for bin stretching
• Scheduling with Deadlines and Loss Functions
• Online Scheduling with Bounded Migration
• Better Bounds for Online Scheduling
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Improved Bounds for the Online Scheduling Problem
• On-Line Load Balancing for Related Machines
• Online Makespan Scheduling with Sublinear Advice
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Optimal non-preemptive semi-online scheduling on two related machines
• Semi-online scheduling with decreasing job sizes
• Randomized on-line scheduling on two uniform machines
• Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios
• On-line bin-stretching

This page was built for publication: Parallel solutions for preemptive makespan scheduling on two identical machines