| 带两个服务等级约束的三台机排序问题 |
| |
| 引用本文： | 姚然,张安.带两个服务等级约束的三台机排序问题[J].杭州电子科技大学学报,2014(1):54-56. |
| |
| 作者姓名： | 姚然 张安 |
| |
| 作者单位： | 杭州电子科技大学理学院,浙江杭州310018 |
| |
| 基金项目： | 基金项目：国家自然科学青年基金资助项目（11201105） |
| |
| 摘 要： | 研究带两个服务等级约束的3台同型机在线排序问题。工件和机器的服务等级为1或2,加工允许中断但不允许引入机器空闲时间,目标是最小化最大完工时间。该文首先证明任意在线算法的竞争比至少是3/2,接着对仅有1台机器等级为1的情形给出了竞争比为5/3的在线算法。
|
| 关 键 词： | 排序问题 服务等级 在线算法 竞争比 |
The Scheduling Problem on Three Identical Machines with Two GoS Levels |
| |
| Yao Ran,Zhang An.The Scheduling Problem on Three Identical Machines with Two GoS Levels[J].Journal of Hangzhou Dianzi University,2014(1):54-56. |
| |
| Authors: | Yao Ran Zhang An |
| |
| Affiliation: | Yao Ran, Zhang An |
| |
| Abstract: | We study online scheduling on three identical machines with two grades of service （GoS） levels. Each job , as well as each machine , is associated with a GoS level of either 1 or 2 .Preemption is allowed but machine idle times are forbidden .The objective is to minimize the maximum completion time of jobs .We first show that the competitive ratio of any online algorithm is no smaller than 3/2.Then, for the problem when only one machine has a GoS level of 1, we propose a 5/3-competitive algorithm. |
| |
| Keywords: | scheduling grade of service online algorithm competitive ratio |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
