title: Semi-online scheduling on two machines with GoS levels and partial information of processing time.
abstract: This paper investigates semi-online scheduling problems on two parallel machines under a grade of service (GoS) provision subject to minimize the makespan. We consider three different semi-online versions with knowing the total processing time of the jobs with higher GoS level, knowing the total processing time of the jobs with lower GoS level, or knowing both in advance. Respectively, for the three semi-online versions, we develop algorithms with competitive ratios of 3/2, 20/13, and 4/3 which are shown to be optimal.
authors.affiliation: Business School, Sichuan University, Chengdu 610065, China.
authors.forename: Taibo
authors.identifier: 0000-0002-2817-8746
authors.initials: T
authors.lastname: Luo
authors.affiliation: Business School, Sichuan University, Chengdu 610065, China ; State Key Lab for Manufacturing Systems Engineering, Xi'an 710049, China.
authors.forename: Yinfeng
authors.identifier: 0000-0002-8491-7048
authors.initials: Y
authors.lastname: Xu
mesh_terms: D000465:Algorithms; D008962:Models, Theoretical