文献类型：期刊文献

中文题名：An Optimal Online Algorithm for Scheduling on Two Parallel Machines with GoS Eligibility Constraints

作者：Jia Xu[1];Zhao-Hui Liu[1]

机构：[1]Department of Mathematics,East China University of Science and Technology,Shanghai 200237,China

年份：2016

卷号：4

期号：3

起止页码：371

中文期刊名：Journal of the Operations Research Society of China

外文期刊名：中国运筹学会会刊（英文）

收录：Scopus;CSCD:【CSCD2015_2016】；

基金：the National Natural Science Foundation of China(No.11171106).

语种：英文

中文关键词：Scheduling;Parallel machine;Eligibility constraint;Online algorithm

摘要：We consider the online scheduling problem on two parallel machines with the Grade of Service(GoS)eligibility constraints.The jobs arrive over time,and the objective is to minimize the makespan.We develop a(1+α)-competitive optimal algorithm,whereα≈0.555 is a solution ofα^(3)?2α^(2)?α+1=0.