研究了一类应急物资的两台平行机加工排序问题,该物资的时间效用随完工时间n次幂递减。对于最小化完工时间n次方和的目标函数,指出了该类问题是NP-hard。结合经典的SPT(Shortest Processing Time first)算法设计了一种改进算法ISPT,给...研究了一类应急物资的两台平行机加工排序问题,该物资的时间效用随完工时间n次幂递减。对于最小化完工时间n次方和的目标函数,指出了该类问题是NP-hard。结合经典的SPT(Shortest Processing Time first)算法设计了一种改进算法ISPT,给出了该算法的近似比。结果表明:本文设计的算法ISPT在某些特殊情形可以求得最优解,而SPT算法则无法求得最优解。展开更多
文摘研究了一类应急物资的两台平行机加工排序问题,该物资的时间效用随完工时间n次幂递减。对于最小化完工时间n次方和的目标函数,指出了该类问题是NP-hard。结合经典的SPT(Shortest Processing Time first)算法设计了一种改进算法ISPT,给出了该算法的近似比。结果表明:本文设计的算法ISPT在某些特殊情形可以求得最优解,而SPT算法则无法求得最优解。
