Single machine flow-time scheduling with a single breakdown
From MaRDI portal
We consider the problem of scheduling tasks on a single machine to minimize the flowtime. The machine is subject to breakdowns during the processing of the tasks. The breakdowns occur at random times and the machine is unavailable until it is repaired. The times for repair are random and independent of each other and of the breakdown process. A task that is preempted due to a breakdown must be restarted and otherwise preemptions are not allowed. We show in the case of a single breakdown that if the distribution function of the time to breakdown is concave then shortest processing time (SPT) first scheduling stochastically minimizes the flowtime. For the case of multiple breakdowns we show that SPT minimizes the expected flowtime when the times to breakdown are exponentially distributed. If the time for a single breakdown is known before scheduling begins, and the processing times of the tasks are also known, then we show that the problem of deciding whether there is a schedule with flowtime less than or equal to a given value is NP-complete. Finally, we bound the performance of SPT scheduling in the deterministic case when there is a single breakdown.
Recommendations
- Single-machine scheduling subject to stochastic breakdowns
- Optimal rules for single machine scheduling with stochastic breakdowns
- STOCHASTIC SCHEDULING WITH PREEMPTIVE-REPEAT MACHINE BREAKDOWNS TO MINIMIZE THE EXPECTED WEIGHTED FLOW TIME
- Scheduling on a single machine with a single breakdown to minimize stochastically the number of tardy jobs
- Stochastic scheduling subject to machine breakdowns: The preemptive-repeat model with discounted reward and other criteria
Cites work
Cited in
(90)- 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
- Single machine flow-time scheduling with a single breakdown
- On stochastic machine scheduling with general distributional assumptions
- 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
- Joint production and preventive maintenance scheduling for a single degraded machine by considering machine failures
- Fault tolerant scheduling of tasks of two sizes under resource augmentation
- Two-agent supply chain scheduling problem to minimize the sum of the total weighted completion time and batch cost
- Optimal rules for single machine scheduling with stochastic breakdowns
- Robust single machine scheduling with a flexible maintenance activity
- Cost allocation in rescheduling with machine unavailable period
- Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance
- Preemptive scheduling with availability constraints to minimize total weighted completion times
- Match-up scheduling under a machine breakdown
- An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
- The symmetric quadratic knapsack problem: approximation and scheduling applications
- Scheduling with limited machine availability
- Solving the weighted capacitated planned maintenance problem and its variants
- Minimizing total weighted late work on a single-machine with non-availability intervals
- Single machine scheduling with non-availability interval and optional job rejection
- Single-machine scheduling with machine unavailability periods and resource dependent processing times
- Single-machine common due date total earliness/tardiness scheduling with machine unavailability
- Single-machine scheduling problems with machine aging effect and an optional maintenance activity
- 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
- Parallel-machine scheduling under potential disruption
- Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with one planned setup period
- The complexity of machine scheduling for stability with a single disrupted job
- Machine scheduling with an availability constraint
- Minimizing makespan on a single machine subject to random breakdowns
- Evaluation of the expected makespan of a set of non-resumable jobs on parallel machines with stochastic failures
- Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
- An anticipative scheduling approach with controllable processing times
- Replication and sequencing of unreliable jobs on parallel machines
- Approximation algorithms for the single-machine scheduling with a period of maintenance
- A branch-and-bound method for the single-machine scheduling problem under a non-availability constraint for maximum delivery time minimization
- 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
- Semi-online scheduling on a single machine with unexpected breakdown
- Minimising total flow-time on two parallel machines with planned downtimes and resumable jobs
- Rescheduling on identical parallel machines with machine disruptions to minimize total completion time
- Scheduling on a single machine with a single breakdown to minimize stochastically the number of tardy jobs
- STOCHASTIC SCHEDULING WITH ASYMMETRIC EARLINESS AND TARDINESS PENALTIES UNDER RANDOM MACHINE BREAKDOWNS
- SINGLE MACHINE SCHEDULING WITH FORBIDDEN INTERVALS AND JOB DELIVERY TIMES
- Two meta-heuristic algorithms for solving multi-objective flexible job-shop scheduling with parallel machine and maintenance constraints
- A Survey on Approximation Algorithms for Scheduling with Machine Unavailability
- 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
- 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
- Single-machine scheduling subject to stochastic breakdowns
- Integrated production planning and preventive maintenance in deteriorating production systems
- Single-machine scheduling with maintenance and repair rate-modifying activities
- Short‐term scheduling with machine calibration
- 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
- Approximation schemes for parallel machine scheduling with availability constraints
- Single machine scheduling with rejection and a non-availability interval to minimize the maximum delivery completion time plus the total rejection cost
- Single machine scheduling with semi-resumable machine availability constraints
- Single machine lot scheduling with maintenance activity
- Replication and sequencing of unreliable jobs on m parallel machines: new results
- Stochastic single-machine scheduling with workload-dependent maintenance activities
- Sequencing, task failures, and capacity when failures are driven by a non-homogeneous Poisson process
- Scheduling with tool changes to minimize total completion time: Basic results and SPT performance
- 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
- Single machine flow-time scheduling with scheduled maintenance
- Complexity and algorithms for two-stage flexible flowshop scheduling with availability constraints
- Optimal unrestricted dynamic stochastic scheduling with partial losses of work due to breakdowns
- Scheduling for stability in single-machine production systems
- Approximability of single machine scheduling with fixed jobs to minimize total completion time
- Improved algorithms for two single machine scheduling problems
- Scheduling with tool changes to minimize total completion time under controllable machining conditions
- An integrated production and preventive maintenance planning model
- Two machine scheduling under disruptions with transportation considerations
- Supply chain scheduling problem in the hospital with periodic working time on a single machine
- Prioritized surgery scheduling in face of surgeon tiredness and fixed off-duty period
- Job scheduling and management of wearing tools with stochastic tool lifetimes
- Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
This page was built for publication: Single machine flow-time scheduling with a single breakdown
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111018)
