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

DOI10.1016/J.IPL.2010.02.013MaRDI QIDQ991796zbMATH OpenOpenAlexFDO

Authors Jiping Tao, Zhijun Chao, Ye Tao, Yugeng 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 algorithmssingle machine schedulingcompetitive ratiototal 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)

Recommendations

• A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times
• 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 Algorithm for Scheduling on a Batch Processing Machine
• A semi-online algorithm for single machine scheduling with rejection

Cites work

• scientific article; zbMATH DE number 6472636 (Why is no real title available?)
• 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
• Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates
• Minimizing average completion time in the presence of release dates
• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time
• Online algorithms. The state of the art
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Semi-online scheduling jobs with tightly-grouped processing times on three identical machines
• The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates

Cited in

(16)

• Single-machine online scheduling of jobs with non-delayed processing constraint
• Asymptotic Performance Ratio of an Online Algorithm for the Single Machine Scheduling With Release Dates
• Online scheduling to minimize the total weighted completion time plus the rejection cost
• A semi-online algorithm for solving the single machine scheduling problem to minimize total weighted completion time with discounted factor
• A semi-online algorithm for single machine scheduling with rejection
• OPTIMAL SEMI-ONLINE ALGORITHMS FOR m-BATCH-MACHINE FLOW SHOP SCHEDULING
• On competitive analysis for polling systems
• A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time
• Online interval scheduling on a single machine with finite lookahead
• A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection
• An optimal online algorithm for single machine scheduling with bounded delivery times
• A \(2.28\)-competitive algorithm for online scheduling on identical machines
• scientific article; zbMATH DE number 1559094 (Why is no real title available?)
• A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times
• A competitive online algorithm for minimizing total weighted completion time on uniform machines
• Online scheduling with linear deteriorating jobs to minimize the total weighted completion time

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

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