Approximating total flow time on parallel machines
DOI10.1016/J.JCSS.2006.10.018zbMATH Open1120.90022OpenAlexW1998382156MaRDI QIDQ2641865FDOQ2641865
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
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
approximation algorithmscompetitive analysison-line algorithmsparallel machine schedulingflow-time optimization
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)
Cites Work
- Title not available (Why is that?)
- Nonclairvoyant scheduling
- Title not available (Why is that?)
- Title not available (Why is that?)
- Online Scheduling to Minimize Average Stretch
- Online algorithms. The state of the art
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- Title not available (Why is that?)
- Average stretch without migration
- Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines
- Minimizing flow time nonclairvoyantly
- Minimizing total flow time and total completion time with immediate dispatching
- Minimizing the Flow Time Without Migration
- Title not available (Why is that?)
- Algorithms for minimizing weighted flow time
- Title not available (Why is that?)
- Minimizing mean flow time with release time constraint
- A Simpler Proof of Preemptive Total Flow Time Approximation on Parallel Machines
Cited In (25)
- Title not available (Why is that?)
- 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
- From preemptive to non-preemptive scheduling using rejections
- Energy efficient scheduling of parallelizable jobs
- Non-clairvoyantly scheduling to minimize convex functions
- Improved multi-processor scheduling for flow time and energy
- Minimizing flow time on a constant number of machines with preemption
- 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
- A scheduling framework for distributed key-value stores and its application to tail latency minimization
- A Simpler Proof of Preemptive Total Flow Time Approximation on Parallel Machines
- Batching to Minimize Flow Times on Parallel Heterogeneous Machines
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)
