Optimal algorithms for online scheduling with bounded rearrangement at the end

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

zbMATH Keywords

upper boundslower boundsonline schedulingonline scheduling with bounded rearrangement at the end (BRE)

Mathematics Subject Classification ID

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)

A survey on makespan minimization in semi-online environments ⋮ The geodesic distance on the generalized gamma manifold for texture image retrieval ⋮ ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER ⋮ Semi-online scheduling: a survey ⋮ Multisource Single-Cell Data Integration by MAW Barycenter for Gaussian Mixture Models ⋮ Parallel solutions for preemptive makespan scheduling on two identical machines ⋮ Scheduling on parallel identical machines with late work criterion: offline and online cases ⋮ Online scheduling with one rearrangement at the end: revisited ⋮ Online Makespan Scheduling with Job Migration on Uniform Machines ⋮ Optimal transport natural gradient for statistical manifolds with continuous sample space ⋮ A mean field games approach to cluster analysis ⋮ Online makespan scheduling with job migration on uniform machines ⋮ Summary statistics and discrepancy measures for approximate Bayesian computation via surrogate posteriors ⋮ Online scheduling with migration on two hierarchical 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
• 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