Online minimum makespan scheduling with a buffer

DOI10.1142/S0129054114500191MaRDI QIDQ2929632zbMATHOpenAlexFDO

Authors Ning Ding, Yan Lan, Xin Chen, György Dósa, He Guo, Xin Han

Publication date 14 November 2014

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054114500191

zbMATH Keywords

competitive ratioonline schedulingbuffer

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• Online minimum makespan scheduling with a buffer
• Online scheduling with a buffer on related machines
• Makespan minimization in online scheduling with machine eligibility
• Makespan minimization in online scheduling with machine eligibility
• Improved semi-online makespan scheduling with a reordering buffer
• Online scheduling on unbounded parallel-batch machines to minimize the makespan
• scientific article; zbMATH DE number 1947443
• Online scheduling on an unbounded parallel-batch machine and a standard machine to minimize makespan

Cites work

• A Better Algorithm for an Ancient Scheduling Problem
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• A simple semi on-line algorithm for \(\mathrm{P}2//C_{\max}\) with a buffer
• Better Bounds for Online Scheduling
• Bounds on Multiprocessing Timing Anomalies
• Improved Bounds for the Online Scheduling Problem
• Improved semi-online makespan scheduling with a reordering buffer
• New algorithms for an ancient scheduling problem.
• On-Line Load Balancing for Related Machines
• On-line scheduling revisited
• Online scheduling on two uniform machines to minimize the makespan
• Online scheduling with bounded migration
• Online scheduling with rearrangement on two related machines
• Online scheduling with reassignment
• Optimal algorithms for online scheduling with bounded rearrangement at the end
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• Semi on-line algorithms for the partition problem
• Tighter Bounds for LPT Scheduling on Uniform Processors

Cited in

(14)

• A survey on makespan minimization in semi-online environments
• Online Sorting Buffers on Line
• Max-min online allocations with a reordering buffer
• scientific article; zbMATH DE number 1754640 (Why is no real title available?)
• Improved semi-online makespan scheduling with a reordering buffer
• Online scheduling with rejection and reordering: exact algorithms for unit size jobs
• Online minimum makespan scheduling with a buffer
• Online scheduling with a buffer on related machines
• Online makespan scheduling with job migration on uniform machines
• Online bin packing problem with buffer and bounded size revisited
• Semi-online scheduling: a survey
• Buffer minimization with conflicts on a line
• Max-min online allocations with a reordering buffer
• Online Makespan Scheduling with Job Migration on Uniform Machines

This page was built for publication: Online minimum makespan scheduling with a buffer

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