Optimal algorithms for online scheduling with bounded rearrangement at the end

DOI10.1016/J.TCS.2011.07.014MaRDI QIDQ653317zbMATH OpenOpenAlexWikidataFDO

Authors Xin Chen, Yan Lan, Attila Benko, György Dósa, Xin Han

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

lower boundsonline schedulingupper boundsonline scheduling with bounded rearrangement at the end (BRE)

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) 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)

Recommendations

• Online scheduling with rearrangement on two related machines
• Online scheduling with one rearrangement at the end: revisited
• Online scheduling with reassignment on two uniform machines
• Semi-online hierarchical scheduling problems with buffer or rearrangements
• Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines

Cites work

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

Cited in

(17)

• A survey on makespan minimization in semi-online environments
• The geodesic distance on the generalized gamma manifold for texture image retrieval
• Online scheduling with rearrangement on two related machines
• Optimal transport natural gradient for statistical manifolds with continuous sample space
• A mean field games approach to cluster analysis
• Multisource Single-Cell Data Integration by MAW Barycenter for Gaussian Mixture Models
• Online scheduling with migration on two hierarchical machines
• Projection-based techniques for high-dimensional optimal transport problems
• Summary statistics and discrepancy measures for approximate Bayesian computation via surrogate posteriors
• Online minimum makespan scheduling with a buffer
• Scheduling on parallel identical machines with late work criterion: offline and online cases
• Distributionally robust optimization using optimal transport for Gaussian mixture models
• Online makespan scheduling with job migration on uniform machines
• Semi-online scheduling: a survey
• Parallel solutions for preemptive makespan scheduling on two identical machines
• Online scheduling with one rearrangement at the end: revisited
• Online Makespan Scheduling with Job Migration on Uniform Machines

This page was built for publication: Optimal algorithms for online scheduling with bounded rearrangement at the end

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q653317)