A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs

DOI10.1023/A:1009626427432zbMath0903.90100MaRDI QIDQ1388066

Mikhail Y. Kovalyov, Wiesław X. Kubiak

Publication date: 5 January 1999

Published in: Journal of Heuristics (Search for Journal in Brave)

zbMATH Keywords

deteriorating jobs; single machine; makespan; fully polynomial approximation scheme

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

Related Items

SCHEDULING JOBS WITH PROCESSING TIMES DEPENDENT ON POSITION, STARTING TIME, AND ALLOTTED RESOURCE, An approximation algorithm for parallel machine scheduling with simple linear deterioration, A Faster FPTAS for a Supply Chain Scheduling Problem to Minimize Holding Costs with Outsourcing, Common due date assignment and single-machine scheduling with release times to minimize the weighted number of tardy jobs, Due date assignment and single machine scheduling with deteriorating jobs to minimize the weighted number of tardy jobs, 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, Uniform parallel-machine scheduling with time dependent processing times, Scheduling of deteriorating jobs with release dates to minimize the maximum lateness, Parallel-machine scheduling with deteriorating jobs and rejection, Parallel-machine scheduling of simple linear deteriorating jobs, An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan, A scheduling problem with job values given as a power function of their completion times, An FPTAS for parallel-machine scheduling under a grade of service provision to minimize makespan, ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation, Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan, A concise survey of scheduling with time-dependent processing times, Coordination mechanisms for scheduling games with proportional deterioration, Scheduling with time-dependent discrepancy times, A local search algorithm: minimizing makespan of deteriorating jobs with relaxed agreeable weights, Bounded parallel-batch scheduling on single and multi machines for deteriorating jobs, Variable neighborhood search for parallel machines scheduling problem with step deteriorating jobs, Parallel machines scheduling with deteriorating jobs and availability constraints, Single-machine batch scheduling of linear deteriorating jobs, Deteriorating jobs scheduling on a single machine with release dates, rejection and a fixed non-availability interval, Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance, Parallel-machine scheduling with simple linear deterioration to minimize total completion time, An FPTAS for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs, Single Machine Scheduling with an Availability Constraint and Rejection, Scheduling Deteriorating Jobs with Availability Constraints to Minimize the Makespan, The Coordination of Two Parallel Machines Scheduling and Batch Deliveries