Single machine flow-time scheduling with scheduled maintenance
From MaRDI portal
We investigate a single machine scheduling problem of minimizing the sum of job flow times subject to scheduled maintenance. We first provide NP- completeness proof for the problem. This proof is much shorter than the one given in the literature. The Shortest Processing Time (SPT) sequence is then shown to have a worst case error bound of 2/7. Furthermore, an example is provided to show that the bound is tight.
Recommendations
- Single machine scheduling with preventive maintenances
- Flow shops with machine maintenance: ordered and proportionate cases
- Some results of scheduling with multi-phase maintenances on two identical machines
- Scheduling the maintenance on a single machine
- Single-machine scheduling with flexible and periodic maintenance
Cites work
Cited in
(69)- Exponential inapproximability and FPTAS for scheduling with availability constraints
- 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
- Two-machine flowshop scheduling with availability constraints
- Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint
- Machine scheduling with a rate-modifying activity
- Minimizing the makespan on a single machine with flexible maintenances and jobs' release dates
- Maintenance scheduling problem with fuzzy random time windows on a single machine
- Robust single machine scheduling with a flexible maintenance activity
- Cost allocation in rescheduling with machine unavailable period
- Match-up scheduling under a machine breakdown
- An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
- Scheduling with limited machine availability
- Single-machine scheduling with learning effects and maintenance: a methodological note on some polynomial-time solvable cases
- Minimizing total weighted late work on a single-machine with non-availability intervals
- Single-machine scheduling with maintenance activities and rejection
- Single-machine scheduling with machine unavailability periods and resource dependent processing times
- A note on minimizing total weighted completion time with an unexpected machine unavailable interval
- Single-machine scheduling with job-dependent machine deterioration
- Heuristics for the single machine weighted sum of completion times scheduling problem with periodic maintenance
- Single machine predictive scheduling using inserted idle times
- Improved approximation for non-preemptive single machine flow-time scheduling with an availability constraint
- Single machine unbounded parallel-batch scheduling with forbidden intervals
- Minimizing maximum earliness and number of tardy jobs in the single machine scheduling problem with availability constraint
- Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times
- Single machine scheduling under potential disruption
- Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with one planned setup period
- Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan
- Parallel-machine scheduling with potential disruption and positional-dependent processing times
- Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
- Machine scheduling performance with maintenance and failure
- An anticipative scheduling approach with controllable processing times
- Approximation algorithms for the single-machine scheduling with a period of maintenance
- Single Machine Scheduling with an Availability Constraint and Rejection
- Single machine scheduling with an operator non-availability period to minimize total completion time
- Single machine scheduling with linear deteriorating jobs under predictive disruption
- Single machine scheduling with preventive maintenances
- Minimising total flow-time on two parallel machines with planned downtimes and resumable jobs
- Patient scheduling with periodic deteriorating maintenance on single medical device
- Online and semi-online scheduling to minimize makespan on single machine with an availability constraint
- Minimizing total weighted completion time with an unexpected machine unavailable interval
- Parallel machines scheduling with machine maintenance for minsum criteria
- 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
- Rescheduling for machine disruption to minimize makespan and maximum lateness
- scientific article; zbMATH DE number 1389747 (Why is no real title available?)
- Complexity and approximation of single machine scheduling with an operator non-availability period to minimize total completion time
- Scheduling with variable time slot costs
- Some results of scheduling with multi-phase maintenances on two identical machines
- A heuristic approach for a scheduling problem with periodic maintenance and sequence-dependent setup times
- A single machine scheduling problem with availability constraints and sequence-dependent setup costs
- Single-machine scheduling with maintenance and repair rate-modifying activities
- Short‐term scheduling with machine calibration
- Minimizing tardiness scheduling measures with generalized due-dates and a maintenance activity
- Minimizing total completion time on a single machine with a flexible maintenance activity
- Approximation schemes for parallel machine scheduling with availability constraints
- Single-machine scheduling with fixed periodic preventive maintenance to minimise the total weighted completion times
- Solving the single-machine scheduling problem with periodical resource constraints
- Single machine lot scheduling with maintenance activity
- Scheduling with tool changes to minimize total completion time: Basic results and SPT performance
- Two-machine flow shop and open shop scheduling problems with a single maintenance window
- 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
- Approximability of single machine scheduling with fixed jobs to minimize total completion time
- Single-machine scheduling with periodic maintenance to minimize makespan
- Improved algorithms for two single machine scheduling problems
- Scheduling with tool changes to minimize total completion time under controllable machining conditions
- Supply chain scheduling problem in the hospital with periodic working time on a single machine
- Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance
This page was built for publication: Single machine flow-time scheduling with scheduled maintenance
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q811593)
