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

作者：李鹏举; 戴军; 高芳征

来源：数学的实践与认识, 2010, (24): 99-103.

• 调度
• 半在线算法
• 竞争比
• 准备时间 schedule
• semi on-line algorithms
• competitive ratio
• available time

研究调度问题上机器服务总时间已知的问题,针对机器的速度和准备时间不同,分析研究带机器准备时间的服务总时间已知的两台同类机半在线调度优化问题.目标为最小化最大机器服务时间,对于机器服务所有工件的时间已知的半在线情形,给出了人一个竞争比不超过2(s 1)/(2s 1)的半在线算法,其中s_i为机器速度,s_1=1,s_2=s>1.

• 单位
  安阳师范学院; 苏州工业园区服务外包职业学院