Online scheduling with rearrangement on two related machines

DOI10.1016/J.TCS.2010.10.019MaRDI QIDQ627161zbMATH OpenOpenAlexFDO

Authors György Dósa, Xin Han, He Guo, Yuxin 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

Online algorithms; streaming algorithms (68W27) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

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

Cites work

• A Better Algorithm for an Ancient Scheduling Problem
• A simple semi on-line algorithm for \(\mathrm{P}2//C_{\max}\) with a buffer
• Better Bounds for Online Scheduling
• Improved Bounds for the Online Scheduling Problem
• New algorithms for an ancient scheduling problem.
• On-line scheduling revisited
• 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 reassignment
• Online scheduling with reassignment on two uniform machines
• 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

(15)

• A survey on makespan minimization in semi-online environments
• General parametric scheme for the online uniform machine scheduling problem with two different speeds
• Online Order Scheduling Problem with the Same Order Size on Two Identical Machines
• scientific article; zbMATH DE number 5951614 (Why is no real title available?)
• Semi-online hierarchical scheduling problems with buffer or rearrangements
• Optimal algorithms for online scheduling with bounded rearrangement at the end
• Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines
• Online scheduling with rejection and withdrawal
• Semi-online scheduling on two uniform parallel machines with initial lookahead
• Online minimum makespan scheduling with a buffer
• Online interval scheduling on two related machines: the power of lookahead
• Online makespan scheduling with job migration on uniform machines
• Semi-online scheduling: a survey
• Online scheduling with one rearrangement at the end: revisited
• Online Makespan Scheduling with Job Migration on Uniform Machines

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

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