单台批处理机总加权完成时间最小化的启发式算法

摘要

批处理机总加权完成时间最小化问题的复杂性目前还没有确定,因此有必要研究该问题的启发式算法.基于对该问题最优解性质的分析,提出了工件分批的最优性质.分别基于W SPT规则和SPT规则对工件进行总排序,利用工件最优分批性质进行分批,提出了两种启发式算法(简称为W SPTS和SPTS).为了检验算法的性能,将提出的算法与此问题的基准算法和常规算法进行了比较,结果表明,启发式算法W SPTS要优于其他的算法,而SPTS算法的性能最优.