具有服务质量等级和部分处理时间信息的两台机器上的半在线调度
Semi-online scheduling on two machines with GoS levels and partial information of processing time.
作者信息
Luo Taibo, Xu Yinfeng
机构信息
Business School, Sichuan University, Chengdu 610065, China.
Business School, Sichuan University, Chengdu 610065, China ; State Key Lab for Manufacturing Systems Engineering, Xi'an 710049, China.
出版信息
ScientificWorldJournal. 2014 Feb 11;2014:576234. doi: 10.1155/2014/576234. eCollection 2014.
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.
本文研究了在服务等级（GoS）规定下两台并行机器上的半在线调度问题，目标是最小化完工时间。我们考虑三种不同的半在线版本，分别是提前知道具有较高GoS等级的作业的总处理时间、提前知道具有较低GoS等级的作业的总处理时间，或者提前知道两者。对于这三种半在线版本，我们分别开发了竞争比为3/2、20/13和4/3的算法，这些算法被证明是最优的。
Zotero 插件