摘要
讨论了带有可控性维护的单机调度问题,目标是实现工件加权完成时间和的最小化．此问题是强 NP难的,因此给出了三个启发式算法和一个分枝定界算法,并通过实验对这些算法进行评价．实验结果表明其中的两个启发式算法(WSPT算法和综合算法)能得到比较好的近似最优解,分枝定界算法对小规模(n≤10)的问题很容易得到最优解．
In this paper, a single-machine scheduling problem with controllable maintenance is discussed; the objective is to minimize the total weighted completion. The problem is NP-hard in the strong sense. Thus, three heuristic algorithms and a branch and bound algorithm are proposed and the algorithms are evaluated by computational experiments. Computational results show that favorable near optimal solutions can be obtained by two of the heuristic algorithms （the WSPT algorithm and the Integration algorithm） and optimal solutions for small sized problems （n≤10） can easily be derived by the branch and bound algorithm.
出处
《南开大学学报（自然科学版）》
CAS
CSCD
北大核心
2006年第1期36-42,共7页
Acta Scientiarum Naturalium Universitatis Nankaiensis
基金
国家自然科学基金(69674013)
国家攀登计划(910211017)
关键词
调度
维护
启发式算法
分枝定界算法
scheduling
maintenance
heuristic algorithm
branch and bound algorithm
