论文部分内容阅读
研究的目的在于解决实践中对多组任务的优化排序问题，即在最短的时间内完成所有给定的任务。由于这类问题往往都是NP完全问题，人们通常寻求其近似算法。提出了一种改进的LPT算法，利用“最大相对加工时间”准则和“首先空闲”准则，讨论了将n组工件安排在n台速度不同的专用机，一台速度小于专用机的通用机上的Cmax问题，得到了利用该近似算法所得的解丁与最优解T^＊的一个估计：T/T^＊≤1＋1／∑i∈1 si，其中，青表示在最后完工的工件完工之前，在通用机上至少安排了一个工件的工件组的下标集合。由此得出采用该近似算法对