A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection

作者：

Highlights：

• Semi-online scheduling with rejection on identical parallel machines.

• Minimizing the total completion time plus penalty cost.

• The approach “Improved Instance Reduction”.

• Semi-online algorithm with a competitive ratio of 1+1+γ(γ−1)−1γ

摘要

•Semi-online scheduling with rejection on identical parallel machines.•Minimizing the total completion time plus penalty cost.•The approach “Improved Instance Reduction”.•Semi-online algorithm with a competitive ratio of 1+1+γ(γ−1)−1γ

论文关键词：Scheduling,Competitive analysis,Semi-online algorithm,Rejection,Parallel machines

论文评审过程：Received 26 November 2019, Revised 6 May 2020, Accepted 5 September 2020, Available online 5 November 2020, Version of Record 5 November 2020.

论文官网地址：https://doi.org/10.1016/j.amc.2020.125670