Semi-on-line multiprocessor scheduling with given total processing time

DOI10.1016/j.tcs.2004.11.018zbMath1087.68015OpenAlexW2069980502MaRDI QIDQ557814

Hans Kellerer, Vladimir Kotov, Cheng, T. C. Edwin

Publication date: 30 June 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10397/632

zbMATH Keywords

multiprocessor schedulingon-line algorithmsapproximation algorithms

Mathematics Subject Classification ID

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

Related Items (24)

A survey on makespan minimization in semi-online environments ⋮ Online makespan minimization with parallel schedules ⋮ Online makespan minimization with budgeted uncertainty ⋮ Tight upper bounds for semi-online scheduling on two uniform machines with known optimum ⋮ Semi-online machine covering on two uniform machines with known total size ⋮ Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence ⋮ Optimal semi-online algorithms for machine covering ⋮ Semi-online scheduling: a survey ⋮ Semi-online scheduling problems on two identical machines with inexact partial information ⋮ Semi-online scheduling problems on a small number of machines ⋮ Bin stretching with migration on two hierarchical machines ⋮ An efficient algorithm for semi-online multiprocessor scheduling with given total processing time ⋮ Semi-online scheduling revisited ⋮ Optimal algorithms for semi-online machine covering on two hierarchical machines ⋮ An efficient algorithm for bin stretching ⋮ Online over time scheduling on parallel-batch machines: a survey ⋮ Scheduling In the random-order model ⋮ Online bin stretching with bunch techniques ⋮ Best semi-online algorithms for unbounded parallel batch scheduling ⋮ Machine covering with combined partial information ⋮ Two semi-online scheduling problems on two uniform machines ⋮ 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 ⋮ Online bin packing with advice

Cites Work

• Unnamed Item
• Unnamed Item
• Online algorithms. The state of the art
• Semi on-line algorithms for the partition problem
• Bin stretching revisited
• On-line scheduling revisited
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• On-line bin-stretching

This page was built for publication: Semi-on-line multiprocessor scheduling with given total processing time