Designing PTASs for MIN-SUM scheduling problems

DOI10.1016/j.dam.2005.05.014zbMath1120.90014OpenAlexW1990537722MaRDI QIDQ2489956

Foto N. Afrati, Ioannis Milis

Publication date: 28 April 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.05.014

zbMATH Keywords

SchedulingApproximation algorithmsMIN-SUM criteriaPTASs

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (3)

Competitive analysis of preemptive single-machine scheduling ⋮ Approximability of average completion time scheduling on unrelated machines ⋮ A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Formulating the single machine sequencing problem with release dates as a mixed integer program
• Tighter bounds on a heuristic for a partition problem
• A PTAS for the average weighted completion time problem on unrelated machines.
• The power of \(\alpha\)-points in preemptive single machine scheduling.
• Structure of a simple scheduling polyhedron
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
• Single Machine Scheduling with Release Dates
• A PTAS for minimizing the weighted sum of job completion times on parallel machines
• Convex quadratic and semidefinite programming relaxations in scheduling
• Approximation schemes for preemptive weighted flow time
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
• Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem
• An algorithm for the single machine sequencing problem with precedence constraints
• Algorithms for Scheduling Independent Tasks
• Flowshop and Jobshop Schedules: Complexity and Approximation
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Minimizing total completion time in two-processor task systems with prespecified processor allocations
• Algorithms for minimizing weighted flow time
• Bounds for Certain Multiprocessing Anomalies

This page was built for publication: Designing PTASs for MIN-SUM scheduling problems