Designing PTASs for MIN-SUM scheduling problems

DOI10.1016/J.DAM.2005.05.014MaRDI QIDQ2489956zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

SchedulingApproximation algorithmsMIN-SUM criteriaPTASs

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

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

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 1187164 (Why is no real title available?)
• scientific article; zbMATH DE number 1187165 (Why is no real title available?)
• scientific article; zbMATH DE number 1187167 (Why is no real title available?)
• scientific article; zbMATH DE number 176780 (Why is no real title available?)
• scientific article; zbMATH DE number 1256760 (Why is no real title available?)
• scientific article; zbMATH DE number 1261808 (Why is no real title available?)
• scientific article; zbMATH DE number 1303587 (Why is no real title available?)
• scientific article; zbMATH DE number 1305477 (Why is no real title available?)
• scientific article; zbMATH DE number 1305495 (Why is no real title available?)
• scientific article; zbMATH DE number 1305540 (Why is no real title available?)
• scientific article; zbMATH DE number 1305545 (Why is no real title available?)
• scientific article; zbMATH DE number 1003241 (Why is no real title available?)
• scientific article; zbMATH DE number 1167865 (Why is no real title available?)
• scientific article; zbMATH DE number 1182758 (Why is no real title available?)
• scientific article; zbMATH DE number 2080224 (Why is no real title available?)
• scientific article; zbMATH DE number 1559527 (Why is no real title available?)
• scientific article; zbMATH DE number 1754639 (Why is no real title available?)
• scientific article; zbMATH DE number 1754641 (Why is no real title available?)
• scientific article; zbMATH DE number 1754642 (Why is no real title available?)
• scientific article; zbMATH DE number 1757967 (Why is no real title available?)
• scientific article; zbMATH DE number 1757970 (Why is no real title available?)
• scientific article; zbMATH DE number 1839475 (Why is no real title available?)
• scientific article; zbMATH DE number 871909 (Why is no real title available?)
• scientific article; zbMATH DE number 1405788 (Why is no real title available?)
• scientific article; zbMATH DE number 6472625 (Why is no real title available?)
• scientific article; zbMATH DE number 6472638 (Why is no real title available?)
• A PTAS for minimizing the weighted sum of job completion times on parallel machines
• A PTAS for the average weighted completion time problem on unrelated machines.
• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
• Algorithms for Scheduling Independent Tasks
• Algorithms for minimizing weighted flow time
• An algorithm for the single machine sequencing problem with precedence constraints
• Approximation schemes for preemptive weighted flow time
• Bounds for Certain Multiprocessing Anomalies
• Convex quadratic and semidefinite programming relaxations in scheduling
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
• Flowshop and Jobshop Schedules: Complexity and Approximation
• Formulating the single machine sequencing problem with release dates as a mixed integer program
• Minimizing total completion time in two-processor task systems with prespecified processor allocations
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Single machine scheduling with release dates
• Structure of a simple scheduling polyhedron
• The power of \(\alpha\)-points in preemptive single machine scheduling.
• Tighter bounds on a heuristic for a partition problem
• Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem

Cited in

(5)

• scientific article; zbMATH DE number 1839470 (Why is no real title available?)
• Competitive analysis of preemptive single-machine scheduling
• A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem
• scientific article; zbMATH DE number 1982192 (Why is no real title available?)
• Approximability of average completion time scheduling on unrelated machines

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)