A note on worst-case performance of heuristics for maintenance scheduling problems

DOI10.1016/J.DAM.2006.06.005MaRDI QIDQ868400zbMATH OpenOpenAlexFDO

Authors Xiangtong Qi

Publication date 2 March 2007

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2006.06.005

zbMATH Keywords

EDD schedulemaintenanceschedulingSPT scheduleworst-case bound

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Recommendations

• A heuristic approach for a scheduling problem with periodic maintenance and sequence-dependent setup times
• Heuristics for the single machine weighted sum of completion times scheduling problem with periodic maintenance
• A note: Simple heuristics for scheduling a maintenance activity on unrelated machines
• Exact and heuristic methods for the selective maintenance problem
• Maintenance scheduling problems as benchmarks for constraint algorithms
• Cost analysis and extension of a simple maintenance-scheduling heuristic
• A note on worst-case analysis of approximation algorithms for a scheduling problem
• A Worst-case Performance of the Shortest-processing-time Heuristic for Single Machine Scheduling

Cites work

• An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
• scientific article; zbMATH DE number 3890754 (Why is no real title available?)
• scientific article; zbMATH DE number 1389747 (Why is no real title available?)
• Minimizing total flow time in the single-machine scheduling problem with periodic maintenance
• Scheduling on uniform parallel machines to minimize maximum lateness
• Scheduling the maintenance on a single machine
• Scheduling with limited machine availability
• Scheduling with tool changes to minimize total completion time: A study of heuristics and their performance
• Scheduling with tool changes to minimize total completion time: Basic results and SPT performance
• Single-machine scheduling with maintenance and repair rate-modifying activities
• Two-machine flowshop scheduling with availability constraints

Cited in

(24)

• A note on ``scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan
• A note: Simple heuristics for scheduling a maintenance activity on unrelated machines
• Single-machine scheduling with workload-dependent tool change durations and equal processing time jobs to minimize total completion time
• Makespan minimization for two parallel machines scheduling with a periodic availability constraint: mathematical programming model, average-case analysis, and anomalies
• Maintenance scheduling problems as benchmarks for constraint algorithms
• Number of bins and maximum lateness minimization in two-dimensional bin packing
• Single-machine scheduling with maintenance activities and rejection
• Single-machine scheduling with job-dependent machine deterioration
• scientific article; zbMATH DE number 6383427 (Why is no real title available?)
• Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval
• Integrated production scheduling and maintenance policy for robustness in a single machine
• Scheduling two parallel machines with machine-dependent availabilities
• SINGLE MACHINE SCHEDULING WITH FORBIDDEN INTERVALS AND JOB DELIVERY TIMES
• Cost analysis and extension of a simple maintenance-scheduling heuristic
• A heuristic approach for a scheduling problem with periodic maintenance and sequence-dependent setup times
• Minimizing total completion time on a single machine with a flexible maintenance activity
• Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates
• Scheduling with periodic availability constraints to minimize makespan
• Open shop scheduling problem with a flexible maintenance period: revisited
• Parallel machine scheduling with periodic availability constraints to minimize makespan
• Single machine scheduling with a restricted weight-modifying activity to minimize the weighted makespan
• Minimizing the total completion time on a single machine with the learning effect and multiple availability constraints
• Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval
• Supply chain scheduling problem in the hospital with periodic working time on a single machine

This page was built for publication: A note on worst-case performance of heuristics for maintenance scheduling problems

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