Approximating total flow time on parallel machines

DOI10.1016/j.jcss.2006.10.018zbMath1120.90022OpenAlexW1998382156MaRDI QIDQ2641865

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

competitive analysison-line algorithmsparallel machine schedulingapproximation algorithmsflow-time optimization

Mathematics Subject Classification ID

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

Related Items

An Optimal Control Framework for Online Job Scheduling with General Cost Functions ⋮ Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time ⋮ Rejecting jobs to minimize load and maximum flow-time ⋮ The consecutive multiprocessor job scheduling problem ⋮ Improved lower bounds for online scheduling to minimize total stretch ⋮ Distributionally robust scheduling algorithms for total flow time minimization on parallel machines using norm regularizations ⋮ A Modern View on Stability of Approximation ⋮ Improved multi-processor scheduling for flow time and energy ⋮ Non-Preemptive Flow-Time Minimization via Rejections ⋮ Scheduling parallel jobs online with convex and concave parallelizability ⋮ Energy efficient scheduling of parallelizable jobs ⋮ Minimizing Average Flow Time on Unrelated Machines ⋮ From Preemptive to Non-preemptive Scheduling Using Rejections ⋮ Non-clairvoyantly scheduling to minimize convex functions ⋮ A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimizing total flow time and total completion time with immediate dispatching
• Minimizing mean flow time with release time constraint
• Online algorithms. The state of the art
• Nonclairvoyant scheduling
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Average stretch without migration
• Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines
• Minimizing the Flow Time Without Migration
• Minimizing flow time nonclairvoyantly
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Online Scheduling to Minimize Average Stretch
• Algorithms for minimizing weighted flow time
• A Simpler Proof of Preemptive Total Flow Time Approximation on Parallel Machines