Online Scheduling on Two Parallel Identical Machines Under a Grade of Service Provision

作     者：Shuang Cai Ke Liu 

作者机构：Data DepartmentBeijing Kingsoft Cloud Network Technology Co.Ltd.Beijing100086China Academy of Mathematics and Systems ScienceChinese Academy of SciencesBeijing100190China University of Chinese Academy of SciencesBeijing100190China 

出 版 物：《Journal of the Operations Research Society of China》 (中国运筹学会会刊（英文）)

年 卷 期：2022年第10卷第4期

页      面：689-702页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：This research was supported by the National Natural Science Foundation of China(Nos.11271356 and 71390334). 

主　　题：Online scheduling Parallel machines A grade of service provision GoS 

摘      要：In this paper,we investigate online scheduling problems on two parallel identical machines under a grade of service provision with makespan as the objective function.The jobs arrive over time and each job can be scheduled only when it has already been arrived.We consider three different versions:(i)the two machines cannot be idle at the same time until all arrived jobs have been processed;(ii)further to the first problem,jobs are processed on a first-come,first-serviced basis;(iii)each job must be assigned to one of the two machines as soon as it arrives.Respectively for three online scheduling problems,optimal online algorithms are proposed with competitive ratio(√5+1)/2,(√5+1)/2 and 5/3.