Approximability of single machine scheduling with fixed jobs to minimize total completion time

DOI10.1016/J.EJOR.2006.01.025zbMATH Open1109.90047OpenAlexW2049084621MaRDI QIDQ857360FDOQ857360

Authors: N. E. Zubov 

Publication date: 14 December 2006

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2006.01.025

Recommendations

• A short note on the approximation of the single machine scheduling problem to minimize makespan with fixed jobs and precedence constraints
• scientific article; zbMATH DE number 1256760
• Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine
• A 1. 47-approximation for a preemptive single-machine scheduling problem
• A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

zbMATH Keywords

schedulingsingle machineprecedence constraintsfixed jobs

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline
• Title not available (Why is that?)
• Single machine flow-time scheduling with a single breakdown
• Complexity of Scheduling under Precedence Constraints
• Single machine flow-time scheduling with scheduled maintenance
• Title not available (Why is that?)
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Machine scheduling with an availability constraint
• Approximability of scheduling with fixed jobs
• Combinatorial optimization. Theory and algorithms

Cited In (7)

• Approximability of scheduling with fixed jobs
• A short note on the approximation of the single machine scheduling problem to minimize makespan with fixed jobs and precedence constraints
• An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation
• Approximation schemes for parallel machine scheduling with availability constraints
• Optimal algorithms for scheduling under time-of-use tariffs

This page was built for publication: Approximability of single machine scheduling with fixed jobs to minimize total completion time

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