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

DOI10.1016/j.ipl.2010.02.013zbMath1209.68070OpenAlexW2043700761MaRDI 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

zbMATH Keywords

analysis of algorithmscompetitive ratiosingle machine schedulingtotal weighted completion timesemi-online algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (7)

A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time ⋮ A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection ⋮ Online scheduling to minimize the total weighted completion time plus the rejection cost ⋮ On competitive analysis for polling systems ⋮ Online scheduling with linear deteriorating jobs to minimize the total weighted completion time ⋮ A \(2.28\)-competitive algorithm for online scheduling on identical machines ⋮ A Semi-Online Algorithm for Single Machine Scheduling 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

This page was built for publication: An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time