An efficient algorithm for semi-online multiprocessor scheduling with given total processing time

DOI10.1007/s10951-015-0430-4zbMath1333.90045OpenAlexW2138849559MaRDI QIDQ906558

Michaël Gabay, Vladimir Kotov, Hans Kellerer

Publication date: 22 January 2016

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

Full work available at URL: https://doi.org/10.1007/s10951-015-0430-4

zbMATH Keywords

multiprocessor schedulingcompetitive analysissemi-online scheduling

Mathematics Subject Classification ID

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

Related Items (11)

A survey on makespan minimization in semi-online environments ⋮ Scheduling with testing on multiple identical parallel machines ⋮ Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence ⋮ Semi-online scheduling: a survey ⋮ Bin stretching with migration on two hierarchical machines ⋮ Parallel solutions for preemptive makespan scheduling on two identical machines ⋮ Online early work maximization on three hierarchical machines with a common due date ⋮ General parametric scheme for the online uniform machine scheduling problem with two different speeds ⋮ An improved parametric algorithm on two-machine scheduling with given lower and upper bounds for the total processing time ⋮ Tight lower bounds for semi-online scheduling on two uniform machines with known optimum ⋮ A Semi-Online Algorithm for Single Machine Scheduling with Rejection

Cites Work

• Unnamed Item
• Semi-online scheduling revisited
• Semi-on-line multiprocessor scheduling with given total processing time
• Semi on-line algorithms for the partition problem
• On-line scheduling revisited
• An efficient algorithm for bin stretching
• The on-line multiprocessor scheduling problem with known sum of the tasks
• Better Algorithms for Online Bin Stretching
• Recent Advances for a Classical Scheduling Problem
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• On-line bin-stretching

This page was built for publication: An efficient algorithm for semi-online multiprocessor scheduling with given total processing time