总服务时间已知的两台同类机调度问题  

Scheduling on Two Uniform Machines with Total Known Time

作　　者：李鹏举[1] 戴军[1] 高芳征[2] 

机构地区：[1]苏州工业园区服务外包职业学院,江苏苏州215123 [2]安阳师范学院数学与统计学院,河南安阳455000

出　　处：《数学的实践与认识》2010年第24期99-103,共5页Mathematics in Practice and Theory

摘　　要：研究调度问题上机器服务总时间已知的问题,针对机器的速度和准备时间不同,分析研究带机器准备时间的服务总时间已知的两台同类机半在线调度优化问题.目标为最小化最大机器服务时间,对于机器服务所有工件的时间已知的半在线情形,给出了人一个竞争比不超过2(s+1)/(2s+1)的半在线算法,其中s_i为机器速度,s_1=1,s_2=s>1.In this paper,we consider a semi on-line scheduling problem on two uniform machine system（different machine speed） with known total processing time,where the objective is to maximized makespan of the schedule.For the case that the total processing time being known in advance,we propose a semi on-line algorithm with the competitive ratio, which is not more than 2（s＋1）/（2s＋1）.

关 键 词：调度 半在线算法 竞争比 准备时间 

分 类 号：O223[理学—运筹学与控制论]