Optimal algorithms for online scheduling with bounded rearrangement at the end
Publication:653317
DOI10.1016/j.tcs.2011.07.014zbMath1230.68051OpenAlexW2016068554WikidataQ63353562 ScholiaQ63353562MaRDI QIDQ653317
György Dósa, Attila Benko, Yan Lan, Xin Han, Xin Chen
Publication date: 9 January 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.07.014
upper boundslower boundsonline schedulingonline scheduling with bounded rearrangement at the end (BRE)
Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)
Related Items (14)
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
- Online scheduling with a buffer on related machines
- Online scheduling with reassignment
- Online scheduling on two uniform machines to minimize the makespan
- Semi on-line algorithms for the partition problem
- 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
- Preemptive Online Scheduling with Reordering
This page was built for publication: Optimal algorithms for online scheduling with bounded rearrangement at the end