Optimal algorithms for online scheduling with bounded rearrangement at the end

DOI10.1016/j.tcs.2011.07.014zbMath1230.68051WikidataQ63353562 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 bounds; lower bounds; online scheduling; online scheduling with bounded rearrangement at the end (BRE)

Mathematics Subject Classification ID

68W40: Analysis of algorithms

90B35: Deterministic scheduling theory in operations research

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W27: Online algorithms; streaming algorithms

Related Items

Online Makespan Scheduling with Job Migration on Uniform Machines, Multisource Single-Cell Data Integration by MAW Barycenter for Gaussian Mixture Models, Parallel solutions for preemptive makespan scheduling on two identical machines, Online scheduling with one rearrangement at the end: revisited, A survey on makespan minimization in semi-online environments, Scheduling on parallel identical machines with late work criterion: offline and online cases, 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, The geodesic distance on the generalized gamma manifold for texture image retrieval, Semi-online scheduling: a survey, ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER

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