An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan

DOI10.1016/J.IPL.2006.11.014MaRDI QIDQ845960zbMATH OpenOpenAlexFDO

Authors Min Ji, T. C. Edwin Cheng

Publication date 29 January 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2006.11.014

zbMATH Keywords

approximation algorithmsmakespanmachine schedulingstart time-dependent processing times

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Recommendations

• Scheduling jobs with piecewise linear decreasing processing times
• Algorithms and Computation
• Parallel-machine scheduling with simple linear deterioration to minimize total completion time
• Single machine scheduling with piecewise linear decreasing processing times and rejection jobs
• An FPTAS for uniform machine scheduling to minimize makespan with linear deterioration

Cites work

• A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem
• A concise survey of scheduling with time-dependent processing times
• A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs
• A note on single-processor scheduling with time-dependent execution times
• Complexity of scheduling tasks with time-dependent execution times
• Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem
• Minimizing the total weighted completion time of deteriorating jobs
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling Deteriorating Jobs on a Single Processor
• Scheduling deteriorating jobs to minimize makespan
• Scheduling jobs with piecewise linear decreasing processing times
• Scheduling start time dependent jobs to minimize the total weighted completion time
• Scheduling with time dependent processing times: Review and extensions
• Scheduling with time-dependent execution times
• V-Shaped Policies for Scheduling Deteriorating Jobs

Cited in

(14)

• A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs
• An FPTAS for parallel-machine scheduling under a grade of service provision to minimize makespan
• Scheduling with time-dependent discrepancy times
• Group scheduling with deteriorating jobs to minimize the total weighted number of late jobs
• Scheduling jobs with a V-shaped time-dependent processing time
• Single-machine batch scheduling of linear deteriorating jobs
• Single-machine scheduling with a nonlinear deterioration function
• Scheduling jobs with piecewise linear decreasing processing times
• Single machine scheduling with piecewise linear decreasing processing times and rejection jobs
• A review of four decades of time-dependent scheduling: main results, new topics, and open problems
• Two FPTAS algorithms of problem \(1|r_j\), dm\(|C_{\max}+TPC\)
• Algorithms and Computation
• Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration
• An FPTAS for uniform machine scheduling to minimize makespan with linear deterioration

This page was built for publication: An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan

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