Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines

Authors:	Email author" target="_blank">Yong?He Email author Yiwei?Jiang

Affiliation:	(1) Department of Mathematics, Zhejiang University, 310027 Hangzhou, P. R. China;(2) State Key Lab of CAD & CG, Zhejiang University, 310027 Hangzhou, P. R. China

Abstract:	This paper investigates two preemptive semi-online scheduling problems to minimize makespan on two uniform machines. In the first semi-online problem, we know in advance that all jobs have their processing times in between p and rp $(p > 0,r\geq 1)$ . In the second semi-online problem, we know the size of the largest job in advance. We design an optimal semi-online algorithm which is optimal for every combination of machine speed ratio $s\geq 1$ and job processing time ratio $r\geq 1$ for the first problem, and an optimal semi-online algorithm for every machine speed ratio $s\geq 1$ for the second problem.Received: 2 December 2003, Published online: 16 January 2004This research is supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, China, and National Natural Science Foundation of China (10271110).

Keywords:
本文献已被 SpringerLink 等数据库收录！