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

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

Scheduling on Two Uniform Machines with Total Known Time

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).