Online scheduling with rearrangement on two related machines

DOI10.1016/j.tcs.2010.10.019zbMath1206.68064OpenAlexW2032691644MaRDI QIDQ627161

He Guo, Xin Han, György Dósa, Yu-Xin Wang

Publication date: 21 February 2011

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.10.019

zbMATH Keywords

competitive analysisscheduling problemsonline non-preemptive scheduling problem

Mathematics Subject Classification ID

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 ⋮ ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER ⋮ Semi-online scheduling: a survey ⋮ Online interval scheduling on two related machines: the power of lookahead ⋮ Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines ⋮ General parametric scheme for the online uniform machine scheduling problem with two different speeds ⋮ Online scheduling with one rearrangement at the end: revisited ⋮ Online scheduling with rejection and withdrawal ⋮ Optimal algorithms for online scheduling with bounded rearrangement at the end ⋮ 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 a buffer on related machines
• Online scheduling with reassignment
• New algorithms for an ancient scheduling problem.
• Online scheduling with reassignment on two uniform machines
• Online scheduling on two uniform machines to minimize the makespan
• Semi on-line algorithms for the partition problem
• On-line scheduling revisited
• 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
• Better Bounds for Online Scheduling
• Improved Bounds for the Online Scheduling Problem
• A Better Algorithm for an Ancient Scheduling Problem
• Preemptive Online Scheduling with Reordering

This page was built for publication: Online scheduling with rearrangement on two related machines