A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times

DOI10.3934/JIMO.2010.6.269MaRDI QIDQ974714zbMATH OpenOpenAlexFDO

Authors Jiping Tao, Zhijun Chao, Yugeng Xi

Publication date 7 June 2010

Published in Journal of Industrial and Management Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3934/jimo.2010.6.269

zbMATH Keywords

online algorithmscompetitive analysissingle machine scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Recommendations

• An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time
• An optimal online algorithm for single machine scheduling with bounded delivery times
• An optimal online algorithm for single machine scheduling to minimize total general completion time
• Semi-online algorithms for parallel machine scheduling problems
• OPTIMAL SEMI-ONLINE ALGORITHM FOR SCHEDULING ON A BATCH PROCESSING MACHINE
• Optimal Semi-online Algorithm for Scheduling on a Batch Processing Machine
• A semi-online algorithm for solving the single machine scheduling problem to minimize total weighted completion time with discounted factor
• Optimal Semi-online Scheduling Algorithms on a Small Number of Machines
• A semi-online algorithm for single machine scheduling with rejection

Cited in

(13)

• Comments on ``Competitive analysis of a better on-line algorithm to minimize total completion time on a single-machine
• A \(2.28\)-competitive algorithm for online scheduling on identical machines
• A competitive online algorithm for minimizing total weighted completion time on uniform machines
• Asymptotic Performance Ratio of an Online Algorithm for the Single Machine Scheduling With Release Dates
• Simulated annealing and genetic algorithm based method for a bi-level \textit{seru} loading problem with worker assignment in \textit{seru} production systems
• A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection
• On competitive analysis for polling systems
• Online scheduling with linear deteriorating jobs to minimize the total weighted completion time
• An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time
• A semi-online algorithm for single machine scheduling with rejection
• A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time
• Semi-online scheduling: a survey
• Online scheduling to minimize the total weighted completion time plus the rejection cost

This page was built for publication: A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q974714)