Rejecting jobs to minimize load and maximum flow-time
作者：
Highlights：
• A novel rejection model proposed for online job scheduling where online algorithm may reject ϵ-fraction of requests.
• We consider the restricted assignment setting where each job can be assigned only to a subset of machines.
• O(log21/ϵ)-competitive algorithm presented for minimizing the maximum load on any machine.
• O(1/ϵ4)-competitive algorithm presented for the problem of minimizing the maximum weighted flow-time.
• Above result can be extended for the objective of minimizing the maximum stretch.
摘要
•A novel rejection model proposed for online job scheduling where online algorithm may reject ϵ-fraction of requests.•We consider the restricted assignment setting where each job can be assigned only to a subset of machines.•O(log21/ϵ)-competitive algorithm presented for minimizing the maximum load on any machine.•O(1/ϵ4)-competitive algorithm presented for the problem of minimizing the maximum weighted flow-time.•Above result can be extended for the objective of minimizing the maximum stretch.
论文关键词：Online job scheduling,Restricted assignment,Flow-time,Rejection model,Competitive ratio
论文评审过程：Received 2 April 2016, Accepted 13 July 2017, Available online 1 September 2017, Version of Record 5 October 2017.
论文官网地址：https://doi.org/10.1016/j.jcss.2017.07.006
