Online scheduling with one rearrangement at the end: revisited

DOI10.1016/J.IPL.2012.05.009zbMath1248.68125OpenAlexW2094285533MaRDI QIDQ456073

Xin Han, Xin Chen, He Guo, Cecilia Sik Lanyi, Attila Benko, György Dósa, Yu-Xin Wang

Publication date: 23 October 2012

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

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

zbMATH Keywords

online algorithmscompetitive ratioscheduling problems

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27)

Related Items (4)

A survey on makespan minimization in semi-online environments ⋮ General parametric scheme for the online uniform machine scheduling problem with two different speeds ⋮ Online Makespan Scheduling with Job Migration on Uniform Machines ⋮ Online makespan scheduling with job migration on uniform machines

Cites Work

• A simple semi on-line algorithm for \(\mathrm{P}2//C_{\max}\) with a buffer
• Online scheduling with rearrangement on two related machines
• Optimal algorithms for online scheduling with bounded rearrangement at the end
• Online scheduling with a buffer on related machines
• Online scheduling with reassignment
• Online scheduling on two uniform machines to minimize the makespan
• Online Scheduling with Bounded Migration
• The Power of Reordering for Online Minimum Makespan Scheduling
• `` Strong NP-Completeness Results
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

This page was built for publication: Online scheduling with one rearrangement at the end: revisited