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

DOI10.1016/j.ipl.2006.11.014zbMath1184.68125OpenAlexW2048309541MaRDI QIDQ845960

Min Ji, Cheng, T. C. Edwin

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

machine schedulingmakespanapproximation algorithmsstart time-dependent processing times

Mathematics Subject Classification ID

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

Related Items (9)

Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration ⋮ Scheduling with time-dependent discrepancy times ⋮ Group scheduling with deteriorating jobs to minimize the total weighted number of late jobs ⋮ A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs ⋮ Scheduling jobs with a V-shaped time-dependent processing time ⋮ Single-machine scheduling with a nonlinear deterioration function ⋮ An FPTAS for parallel-machine scheduling under a grade of service provision to minimize makespan ⋮ A review of four decades of time-dependent scheduling: main results, new topics, and open problems ⋮ Single-machine batch scheduling of linear deteriorating jobs

Cites Work

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

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