Online Single Machine Scheduling to Minimize the Maximum Starting Time

DOI10.1142/S0217595917500221zbMath1379.90007OpenAlexW2752015945MaRDI QIDQ4595323

Ling-Fa Lu, Li-Qi Zhang

Publication date: 30 November 2017

Published in: Asia-Pacific Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0217595917500221

zbMATH Keywords

schedulingcompetitive ratioonline algorithmrestarts

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

Online minimization of the maximum starting time: migration helps, Starting time minimization for the maximum job variant

Cites Work

• Unnamed Item
• A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan
• Minimizing average completion time in the presence of release dates
• Restarts can help in the on-line minimization of the maximum delivery time on a single machine
• Approximation schemes for the min-max starting time problem
• Minimizing the maximum starting time on-line
• On-line algorithms for minimizing makespan on batch processing machines
• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
• Bounds for Certain Multiprocessing Anomalies
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints
• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time
• Minimizing the total completion time on-line on a single machine, using restarts
• On-line scheduling on a single machine: Maximizing the number of early jobs