Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates
From MaRDI portal
Publication:640300
DOI10.1007/S10951-009-0146-4zbMATH Open1222.90016OpenAlexW1996513144MaRDI QIDQ640300FDOQ640300
Authors: Imed Kacem, Hans Kellerer 
Publication date: 18 October 2011
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10951-009-0146-4
Recommendations
- Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval
- Improved approximation for non-preemptive single machine flow-time scheduling with an availability constraint
- Approximation algorithms for single machine scheduling with one unavailability period
- Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals
- scientific article; zbMATH DE number 1256760
Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35)
Cites Work
- Improved algorithms for two single machine scheduling problems
- Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
- Fast approximation algorithm for job sequencing with deadlines
- Algorithms for Scheduling Independent Tasks
- A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem
- Scheduling with release dates on a single machine to minimize total weighted completion time
- Single machine flow-time scheduling with a single breakdown
- An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
- Scheduling with limited machine availability
- Improved approximation for non-preemptive single machine flow-time scheduling with an availability constraint
- Minimizing total flow time in the single-machine scheduling problem with periodic maintenance
- Approximation algorithms for single machine scheduling with one unavailability period
- Scheduling the maintenance on a single machine
- Planning Machine Maintenance in Two-Machine Shop Scheduling
- A note on worst-case performance of heuristics for maintenance scheduling problems
- Improved dynamic programming in connection with an FPTAS for the knapsack problem
- Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval
- Lower bounds for tardiness minimization on a single machine with family setup times
Cited In (11)
- Scheduling jobs and maintenance activities on parallel machines
- Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals
- Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval
- Minimizing total weighted completion time with an unexpected machine unavailable interval
- Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines
- Lagrangian relaxation and column generation-based lower bounds for the \(\text{Pm},h_{j1}\parallel \sum w_iC_i\) scheduling problem
- Complexity and approximation of single machine scheduling with an operator non-availability period to minimize total completion time
- Weighted completion time minimization on a single-machine with a fixed non-availability interval: differential approximability
- Improved approximation for non-preemptive single machine flow-time scheduling with an availability constraint
- Minimizing the maximum lateness for scheduling with release times and job rejection
- Constant factor approximation algorithm for weighted flow-time on a single machine in pseudopolynomial time
This page was built for publication: Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q640300)
