An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints

DOI10.1016/j.ejor.2003.08.026zbMath1065.90041OpenAlexW2045895304WikidataQ57387775 ScholiaQ57387775MaRDI QIDQ1887763

Bernard Penz, Christophe Rapine, Piotr Formanowicz, Chérif Sadfi, Jacek Błażewicz

Publication date: 22 November 2004

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

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

zbMATH Keywords

Approximation algorithm Total completion time Single machine scheduling Availability constraints Worst case analysis

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Complexity and performance of numerical algorithms (65Y20)

Related Items (41)

Scheduling jobs and maintenance activities on parallel machines ⋮ Approximation algorithms for the single-machine scheduling with a period of maintenance ⋮ Minimising total flow-time on two parallel machines with planned downtimes and resumable jobs ⋮ Improved approximation for non-preemptive single machine flow-time scheduling with an availability constraint ⋮ An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints ⋮ Online and semi-online scheduling to minimize makespan on single machine with an availability constraint ⋮ Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications ⋮ Single-machine scheduling with periodic maintenance to minimize makespan ⋮ Minimizing the makespan on a single machine with flexible maintenances and jobs' release dates ⋮ Improved algorithms for two single machine scheduling problems ⋮ Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time ⋮ Minimizing total weighted late work on a single-machine with non-availability intervals ⋮ A note on worst-case performance of heuristics for maintenance scheduling problems ⋮ Single Machine Scheduling with an Availability Constraint and Rejection ⋮ Minimizing total completion time on a single machine with a flexible maintenance activity ⋮ Supply chain scheduling problem in the hospital with periodic working time on a single machine ⋮ Minimizing total weighted completion time with an unexpected machine unavailable interval ⋮ Short‐term scheduling with machine calibration ⋮ The symmetric quadratic knapsack problem: approximation and scheduling applications ⋮ Single-machine scheduling with operator non-availability to minimize total weighted completion time ⋮ Parallel machines scheduling with machine maintenance for minsum criteria ⋮ Minimizing maximum earliness and number of tardy jobs in the single machine scheduling problem with availability constraint ⋮ Scheduling on same-speed processors with at most one downtime on each machine ⋮ Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates ⋮ SINGLE MACHINE SCHEDULING WITH FORBIDDEN INTERVALS AND JOB DELIVERY TIMES ⋮ Lagrangian relaxation and column generation-based lower bounds for the \(\text{Pm},h_{j1}\parallel \sum w_iC_i\) scheduling problem ⋮ Integrated scheduling of production and delivery on a single machine with availability constraint ⋮ Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times ⋮ Single Machine Scheduling with an Operator Non-availability Period to Minimize Total Completion Time ⋮ Complexity and approximation of single machine scheduling with an operator non-availability period to minimize total completion time ⋮ Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with one planned setup period ⋮ Single-machine scheduling with machine unavailability periods and resource dependent processing times ⋮ Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance ⋮ Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications ⋮ A heuristic approach for a scheduling problem with periodic maintenance and sequence-dependent setup times ⋮ Single machine batch scheduling to minimize the sum of total flow time and batch delivery cost with an unavailability interval ⋮ Minimizing the total completion time on a single machine with the learning effect and multiple availability constraints ⋮ Heuristics for the single machine weighted sum of completion times scheduling problem with periodic maintenance ⋮ A Survey on Approximation Algorithms for Scheduling with Machine Unavailability ⋮ Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times ⋮ Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

Cites Work

This page was built for publication: An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints