Preemptive Semi-Online Scheduling with Tightly-Grouped Processing Times  

作　　者：YongHe Yi-WeiJiang 

机构地区：[1]DepartmentofMathematics,ZhejiangUniversity,Hangzhou310027,P.R.China [2]StateKeyLabofCAD＆CG,ZhejiangUniversity,Hangzhou310027,P.R.China

出　　处：《Journal of Computer Science & Technology》2004年第6期733-739,共7页计算机科学技术学报（英文版）

基　　金：国家自然科学基金

摘　　要：This paper investigates a preemptive semi-online scheduling problem onm identical parallel machines wherem=2,3. It is assumed that all jobs have their processing times in betweenp andrp (p > 0,r ≥1). The goal is to minimize the makespan. Best possible algorithms are designed for anyr≥1 whenm=2,3. Keywords semi-online - scheduling - preemption - competitive ratio Regular PaperThis research is supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE. China, and the National Natural Science Foundation of China (Grant Nos. 10271110 and 60021201).Yong He received his B.S., M.S., and Ph.D. degrees all from Zhejiang University in 1989, 1992, 1996, respectively. He is currently a professor and Ph.D. supervisor at Department of Mathematics, Zhejiang University. His current research interests include combinatorial and network optimization, scheduling theory, computational biology, mathematical modeling, etc.Yi-Wei Jiang received his B.S. degree from Zhejiang University in 2002. He is currently a Ph.D. candidate of Zhejiang University. His current interests include scheduling theory and online algorithms.This paper investigates a preemptive semi-online scheduling problem onm identical parallel machines wherem=2,3. It is assumed that all jobs have their processing times in betweenp andrp (p > 0,r ≥1). The goal is to minimize the makespan. Best possible algorithms are designed for anyr≥1 whenm=2,3. Keywords semi-online - scheduling - preemption - competitive ratio Regular PaperThis research is supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE. China, and the National Natural Science Foundation of China (Grant Nos. 10271110 and 60021201).Yong He received his B.S., M.S., and Ph.D. degrees all from Zhejiang University in 1989, 1992, 1996, respectively. He is currently a professor and Ph.D. supervisor at Department of Mathematics, Zhejiang University. His current research interests include combinatorial and network optimization, scheduling theory, computational biology, mathematical modeling, etc.Yi-Wei Jiang received his B.S. degree from Zhejiang University in 2002. He is currently a Ph.D. candidate of Zhejiang University. His current interests include scheduling theory and online algorithms.

关 键 词：SEMI-ONLINE SCHEDULING PREEMPTION competitive ratio 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]