具有通用机的四组工件排序问题* (2005年)

为解决实践中对多组任务的优化排序问题，文中提出了一种改进的最长工作优先安排（LPT）的算法，利用“最大相对加工时间”准则和“首先空闲”准则，讨论了将四组工件安排在四台速度相同的专用机、一台同速度的通用机上的Cmax问题，得到了利用该近似算法所得的解T与最优解T*的一个估计：T/T*≤5/4.结果表明，采用该近似算法对工件排序，在最差情况下要比最优排序多出1/4的时间。