最小化完工时间n次方和的排序优化算法

摘要

This paper studies one scheduling problem on two-parallel machines for emergency jobs which devalue rapidly with ex-ponential function.The goal is to minimize the total completion time of the n-th power of job.We show that the problem is NP-hard,and propose an approximation ISPT algorithm which is the modification of classic SPT (Shortest Processing Time)algo-rithm and prove its approximation ratio.We further prove that the proposed ISPT algorithm is optimal in some special case.%研究了一类应急物资的两台平行机加工排序问题,该物资的时间效用随完工时间 n 次幂递减。对于最小化完工时间 n次方和的目标函数,指出了该类问题是 NP-hard。结合经典的 SPT(Shortest Processing Time first)算法设计了一种改进算法ISPT,给出了该算法的近似比。结果表明：本文设计的算法 ISPT 在某些特殊情形可以求得最优解,而 SPT 算法则无法求得最优解。