一类速度不同的具有m台通用机的n组工件的排序问题

摘要

研究的目的在于解决实践中对多组任务的优化排序同题,即在最短的时间内完成所有给定的任务,由于这类问题往往都是NP完全同题,人们通常寻求其近似算法.文中提出了一种改进的LPT算法,利用"首先空闲"准则,讨论了将n组工件安排在n台速度不同的专用机,m台速度小于专用机的通用机上的Cmax问题,得到了利用该近似算法所得的解T与最优解T*的-个估计:T/T* ≤2+n-2/m+1.