An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time

DOI10.1016/j.ipl.2010.02.013zbMath1209.68070MaRDI QIDQ991796

Jiping Tao, Ye Tao, Zhijun Chao, Yu-Geng Xi

Publication date: 7 September 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.02.013

zbMATH Keywords

analysis of algorithms; competitive ratio; single machine scheduling; total weighted completion time; semi-online algorithms

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

Related Items

A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time, Online scheduling to minimize the total weighted completion time plus the rejection cost, A \(2.28\)-competitive algorithm for online scheduling on identical machines

Cites Work

• Unnamed Item
• Online algorithms. The state of the art
• Minimizing average completion time in the presence of release dates
• The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates
• Semi-online scheduling jobs with tightly-grouped processing times on three identical machines
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
• Asymptotic Performance Ratio of an Online Algorithm for the Single Machine Scheduling With Release Dates
• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time
• Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates