Approximating total flow time on parallel machines

DOI10.1016/J.JCSS.2006.10.018MaRDI QIDQ2641865zbMATH OpenOpenAlexFDO

Authors Danny Raz, Stefano Leonardi

Publication date 23 August 2007

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2006.10.018

zbMATH Keywords

approximation algorithmscompetitive analysisflow-time optimizationon-line algorithmsparallel machine scheduling

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35)

Recommendations

• scientific article; zbMATH DE number 1559527
• SRPT is 1.86-competitive for completion time scheduling
• A Simpler Proof of Preemptive Total Flow Time Approximation on Parallel Machines
• scientific article; zbMATH DE number 1256760
• Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine

Cites work

• A Simpler Proof of Preemptive Total Flow Time Approximation on Parallel Machines
• Algorithms for minimizing weighted flow time
• Average stretch without migration
• scientific article; zbMATH DE number 3757695 (Why is no real title available?)
• scientific article; zbMATH DE number 3633982 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256760 (Why is no real title available?)
• scientific article; zbMATH DE number 2079378 (Why is no real title available?)
• scientific article; zbMATH DE number 1559527 (Why is no real title available?)
• Minimizing flow time nonclairvoyantly
• Minimizing mean flow time with release time constraint
• Minimizing the Flow Time Without Migration
• Minimizing total flow time and total completion time with immediate dispatching
• Nonclairvoyant scheduling
• Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines
• Online algorithms. The state of the art
• Online Scheduling to Minimize Average Stretch
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms

Cited in

(27)

• Improved lower bounds for online scheduling to minimize total stretch
• Scheduling parallel jobs online with convex and concave parallelizability
• Energy efficient scheduling of parallelizable jobs
• Minimizing flow time on a constant number of machines with preemption
• The consecutive multiprocessor job scheduling problem
• Non-clairvoyantly scheduling to minimize convex functions
• A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems
• Rejecting jobs to minimize load and maximum flow-time
• Improved multi-processor scheduling for flow time and energy
• Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time
• Distributionally robust scheduling algorithms for total flow time minimization on parallel machines using norm regularizations
• From preemptive to non-preemptive scheduling using rejections
• Minimizing Average Flow Time on Unrelated Machines
• Batching to Minimize Flow Times on Parallel Heterogeneous Machines
• scientific article; zbMATH DE number 1256760 (Why is no real title available?)
• Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine
• scientific article; zbMATH DE number 1559527 (Why is no real title available?)
• Optimizing busy time on parallel machines
• Non-preemptive flow-time minimization via rejections
• An Optimal Control Framework for Online Job Scheduling with General Cost Functions
• A Simpler Proof of Preemptive Total Flow Time Approximation on Parallel Machines
• On minimizing the total flow time on multiple machines
• Streaming approximation scheme for minimizing total completion time on parallel machines subject to varying processing capacity
• A Modern View on Stability of Approximation
• Two-Agent Scheduling with Resource Augmentation on Multiple Machines
• A scheduling framework for distributed key-value stores and its application to tail latency minimization
• A reduced variable neighborhood search for the just in time job shop scheduling problem with sequence dependent setup times

This page was built for publication: Approximating total flow time on parallel machines

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