Designing PTASs for MIN-SUM scheduling problems

DOI10.1016/J.DAM.2005.05.014zbMATH Open1120.90014OpenAlexW1990537722MaRDI QIDQ2489956FDOQ2489956

Authors: 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

Recommendations

• scientific article; zbMATH DE number 1839470
• scientific article; zbMATH DE number 2102785
• Min-sum scheduling under precedence constraints
• scientific article; zbMATH DE number 2086930
• A PTAS FOR MINIMIZING TOTAL COMPLETION TIME OF BOUNDED BATCH SCHEDULING
• Optimal algorithms and a PTAS for cost-aware scheduling
• A PTAS for minimizing the weighted sum of job completion times on parallel machines
• A PTAS for the P-batch scheduling with \(p_j=p\) to minimize total weighted completion time
• Minimizing completion time for a class of scheduling problems
• FPTAS for half-products minimization with scheduling applications

zbMATH Keywords

SchedulingApproximation algorithmsMIN-SUM criteriaPTASs

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cites Work

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

Cited In (5)

• Competitive analysis of preemptive single-machine scheduling
• Title not available (Why is that?)
• A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem
• Approximability of average completion time scheduling on unrelated machines
• Title not available (Why is that?)

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

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