Semi-online scheduling problems on a small number of machines

DOI10.1007/s10951-013-0329-xzbMath1297.90052OpenAlexW2011620343MaRDI QIDQ398877

Kangbok Lee, Kyungkuk Lim

Publication date: 18 August 2014

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

Full work available at URL: https://doi.org/10.1007/s10951-013-0329-x

zbMATH Keywords

competitive ratiosemi-online schedulinglower bound example

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 (9)

A survey on makespan minimization in semi-online environments ⋮ Tight upper bounds for semi-online scheduling on two uniform machines with known optimum ⋮ Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing ⋮ Semi-online scheduling: a survey ⋮ Bin stretching with migration on two hierarchical machines ⋮ Improved approximation algorithms for multiprocessor scheduling with testing ⋮ Online early work maximization on three hierarchical machines with a common due date ⋮ Tight lower bounds for semi-online scheduling on two uniform machines with known optimum ⋮ Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs

Cites Work

• Unnamed Item
• Unnamed Item
• Semi-online scheduling revisited
• Semi-on-line multiprocessor scheduling with given total processing time
• Semi on-line scheduling on three processors with known sum of the tasks
• New algorithms for an ancient scheduling problem.
• Semi on-line algorithms for the partition problem
• Semi on-line scheduling on two identical machines
• A better lower bound for on-line scheduling
• On-line scheduling revisited
• Semi-on-line problems on two identical machines with combined partial information
• New lower and upper bounds for on-line scheduling
• The on-line multiprocessor scheduling problem with known sum of the tasks
• Optimal Semi-online Scheduling Algorithms on a Small Number of Machines
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• Better Bounds for Online Scheduling
• Improved Bounds for the Online Scheduling Problem
• A Better Algorithm for an Ancient Scheduling Problem
• SEMI-ON-LINE PARALLEL MACHINES SCHEDULING UNDER KNOWN TOTAL AND LARGEST PROCESSING TIMES
• Bounds for Certain Multiprocessing Anomalies
• On-line bin-stretching

This page was built for publication: Semi-online scheduling problems on a small number of machines