An improved semi-online algorithm for scheduling on a single machine with unexpected breakdown

DOI10.1007/s10878-020-00572-6zbMath1445.90039MaRDI QIDQ2185825

Ji Tian, Ruyan Fu, Yan Zhou

Publication date: 5 June 2020

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-020-00572-6

zbMATH Keywords

competitive ratio; semi-online scheduling; unexpected breakdown

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

68W27: Online algorithms; streaming algorithms

Related Items

A Semi-Online Algorithm for Single Machine Scheduling with Rejection

Cites Work

• Unnamed Item
• Semi-online scheduling on a single machine with unexpected breakdown
• Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval
• Minimizing total weighted completion time with an unexpected machine unavailable interval
• Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval
• Approximation algorithms for single machine scheduling with one unavailability period
• An optimal online algorithm for single machine scheduling with bounded delivery times
• Restarts can help in the on-line minimization of the maximum delivery time on a single machine
• Optimal online algorithm for scheduling on two identical machines with machine availability constraints.
• Online scheduling on two parallel machines with release dates and delivery times
• A best on-line algorithm for single machine scheduling with small delivery times
• Machine scheduling with an availability constraint
• SINGLE MACHINE SCHEDULING WITH FORBIDDEN INTERVALS AND JOB DELIVERY TIMES
• PERFORMANCE ANALYSIS OF SIX APPROXIMATION ALGORITHMS FOR THE ONE-MACHINE MAXIMUM LATENESS SCHEDULING PROBLEM WITH READY TIMES
• Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
• Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better
• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine