A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem

DOI10.1016/j.ejor.2009.07.025zbMath1177.90176MaRDI QIDQ1046099

Krzysztof M. Ocetkiewicz

Publication date: 21 December 2009

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

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

zbMATH Keywords

scheduling; deteriorating jobs; single machine; total completion time; FPTAS

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

Related Items

Partial dominated schedules and minimizing the total completion time of deteriorating jobs, An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs

Cites Work

• Unnamed Item
• Complexity analysis of job-shop scheduling with deteriorating jobs
• A concise survey of scheduling with time-dependent processing times
• Parallel machine scheduling with time dependent processing times
• A state-of-the-art review on scheduling with learning effects
• Parallel-machine scheduling with simple linear deterioration to minimize total completion time
• Designing PTASs for MIN-SUM scheduling problems
• Scheduling with time dependent processing times: Review and extensions
• Scheduling Deteriorating Jobs on a Single Processor
• V-Shaped Policies for Scheduling Deteriorating Jobs
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?