An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time
From MaRDI portal
Publication:991796
DOI10.1016/j.ipl.2010.02.013zbMath1209.68070MaRDI QIDQ991796
Ye Tao, Jiping 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
analysis of algorithms; competitive ratio; single machine scheduling; total weighted completion time; semi-online algorithms
68W40: Analysis of algorithms
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
Related Items
A Semi-Online Algorithm for Single Machine Scheduling with Rejection, On competitive analysis for polling systems, A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time, Online scheduling with linear deteriorating jobs 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, A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection
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