Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines

DOI10.1016/J.IPL.2011.01.002zbMath1260.68497OpenAlexW2053402898MaRDI QIDQ1944914

Jing Liu, Xiao Min, Yu-Qing Wang

Publication date: 28 March 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.01.002

zbMATH Keywords

schedulingcompetitive ratiooptimal algorithmreassignment

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35)

Related Items (7)

A survey on makespan minimization in semi-online environments ⋮ On the value of job migration in online makespan minimization ⋮ Semi-online scheduling: a survey ⋮ Bin stretching with migration on two hierarchical machines ⋮ General parametric scheme for the online uniform machine scheduling problem with two different speeds ⋮ Online scheduling with rejection and withdrawal ⋮ Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs

Cites Work

• Unnamed Item
• Unnamed Item
• Online scheduling with rearrangement on two related machines
• Online scheduling with reassignment
• Online scheduling with reassignment on two uniform machines
• Online scheduling on two uniform machines to minimize the makespan
• Semi-on-line problems on two identical machines with combined partial information
• Semi-online algorithms for parallel machine scheduling problems
• A note on on-line scheduling with partial information
• Online Scheduling with Bounded Migration

This page was built for publication: Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines