Randomized On-Line Scheduling Similar Jobs to Minimize Makespan on Two Identical Processors  

作　　者：Dong-lei Du 

机构地区：[1]Faculty of Administration, University of New Brunswick, P.O. Box 4400, Fredericton, NB, E3B 5V4, Canada

出　　处：《Acta Mathematicae Applicatae Sinica》2005年第3期485-488,共4页应用数学学报（英文版）

摘　　要：In this paper we consider an on-line scheduling problem, where jobs with similar processing times within [1, r] arrive one by one to be scheduled in an on-line setting on two identical parallel processors without preemption. The objective is to nlinimize makespan. We devise a randomized on-line algorithm for this problem along with a lower bound.In this paper we consider an on-line scheduling problem, where jobs with similar processing times within [1, r] arrive one by one to be scheduled in an on-line setting on two identical parallel processors without preemption. The objective is to nlinimize makespan. We devise a randomized on-line algorithm for this problem along with a lower bound.

关 键 词：On-line algorithm randomized algorithm SCHEDULING PREEMPTION 

分 类 号：O211.5[理学—概率论与数理统计]