摘要
批处理机总加权完成时间最小化问题的复杂性目前还没有确定,因此有必要研究该问题的启发式算法.基于对该问题最优解性质的分析,提出了工件分批的最优性质.分别基于W SPT规则和SPT规则对工件进行总排序,利用工件最优分批性质进行分批,提出了两种启发式算法(简称为W SPTS和SPTS).为了检验算法的性能,将提出的算法与此问题的基准算法和常规算法进行了比较,结果表明,启发式算法W SPTS要优于其他的算法,而SPTS算法的性能最优.
The problem of n jobs to be processed on single batching machine with a capacity to minimize the total weighted completion time is discussed. An analysis and proof are given for the quality of optimal solution under some condition, based on which two heuristic algorithms are carried out, selecting jobs ordered by WSPT rule （WSPTS） and selecting jobs ordered by SPT rule （SPTS）. To compare the proposed algorithms, heuristic dynamic programming based on WSPT and SPT respectively is carried out, and so does full batch algorithm. The experiment result shows that the heuristic WSPTS is the best one and the SPTS is the most stable one among all the algorithms.
出处
《控制与决策》
EI
CSCD
北大核心
2006年第11期1293-1297,共5页
Control and Decision
基金
国家杰出青年科学基金项目(70425003)
国家自然科学基金项目(70171030
60274049)
高等学校优秀青年教师教学科研奖励计划项目(教育司[2002]383)
