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 analysison-line algorithmsparallel machine schedulingflow-time optimization

Mathematics Subject Classification ID

Randomized algorithms (68W20) 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) Approximation algorithms (68W25)

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

• 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?)
• A Simpler Proof of Preemptive Total Flow Time Approximation on Parallel Machines
• Algorithms for minimizing weighted flow time
• Average stretch without migration
• 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 Scheduling to Minimize Average Stretch
• Online algorithms. The state of the art
• 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

(25)

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

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)