| Preemptive Semi-online Algorithms for Parallel Machine Scheduling with Known Total Size |
| |
| 作者姓名： | Yong HE Hao ZHOU Yi Wei JIANG |
| |
| 作者单位： | [1]Department of Mathematics, Zhejiang University, Hangzhou 310027, P. R. China [2]State Key Lab of CAD ＆ CG, Zhejiang University, Hangzhou 310027, P. R. China |
| |
| 基金项目： | This research is supported by the Teaching and Research Award Program for 0utstanding Young Teachers in Higher Education Institutions of M0E, China, and by National Natural Science Foundation of China （10271110, 60021201） |
| |
| 摘 要： | This paper investigates preemptive semi-online scheduling problems on m identical parallel machines, where the total size of all jobs is known in advance. The goal is to minimize the maximum machine completion time or maximize the minimum machine completion time. For the first objective, we present an optimal semi-online algorithm with competitive ratio 1. For the second objective, we show that the competitive ratio of any semi-online algorithm is at least （2m-3）/（m-1） for any m〉2 and present optimal semi-online algorithms for m = 2, 3.
|
| 关 键 词： | 准在线算法 优先权 竞争分析 优化算法 |
| 收稿时间： | 2004-04-15 |
| 修稿时间： | 2004-04-152005-01-11 |
Preemptive Semi–online Algorithms for Parallel Machine Scheduling with Known Total Size |
| |
| Yong HE Hao ZHOU Yi Wei JIANG.Preemptive Semi-online Algorithms for Parallel Machine Scheduling with Known Total Size[J].Acta Mathematica Sinica,2006,22(2):587-594. |
| |
| Authors: | Yong He Hao Zhou Yi Wei Jiang |
| |
| Institution: | (1) Department of Mathematics, Zhejiang University, Hangzhou 310027, P. R. China;(2) State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310027, P. R. China |
| |
| Abstract: | This paper investigates preemptive semi-online scheduling problems on m identical parallel machines, where the total size of all jobs is known in advance. The goal is to minimize the maximum machine
completion time or maximize the minimum machine completion time. For the first objective, we present an optimal semi–online
algorithm with competitive ratio 1. For the second objective, we show that the competitive ratio of any semi–online algorithm
is at least
for any m > 2 and present optimal semi–online algorithms for m = 2, 3.
This research is supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions
of MOE, China, and by National Natural Science Foundation of China (10271110, 60021201) |
| |
| Keywords: | Semi-online Preemptive scheduling Competitive analysis |
| 本文献已被 维普 SpringerLink 等数据库收录！ |
