基于目标增量的无等待流水调度快速迭代贪婪算法.doc

基于目标增量的无等待流水调度快速迭代贪婪算法 朱夏, 李小平, 王茜 (东南大学计算机科学与工程学院, 南京 210096) (计算机网络和信息集成教育部重点实验室，南京 2100) 摘要: 最小化总完工时间无等待调度是典型的NP-完全问题生产启发式算法两种基本目标增量法快速评估解提出迭代贪婪Iterative Greedy algorithm）求解该问题，构造初始解生成算法，提出分段式重构有哪些信誉好的足球投注网站迭代改进有哪些信誉好的足球投注网站策略进一步提高解的质量。个Benchmark实例将提出的算法与目前该问题好的启发式算法PH1p和元启发式算法进行比较，结果表明在性能优于PH1p，略逊于DPSOvnd；在效率PH1p。 : 无等待流水调度目标增量启发式总完工时间Iterative Greedy Heuristic for No-wait Flowshops with Total Flowtime Minimization Xia Zhu, Xiaoping Li, Qian Wang (School of Computer Science and Engineering, Southeast University, Nanjing, 210096) (Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education, Nanjing,210096) Abstract:?No-wait flowshops with total flowtime minimization are typical NP-Complete combinatorial optimization problems, widely existing in practical manufacturing systems. Different from traditional methods in which objectives are completely computed for a new generated schedule, objective increment methods are presented in this paper. Whether a new schedule is better or worse than the original one is judged just by the objective increment, which can reduce computational time considerably. Objective increment properties are analyzed for fundamental operations of heuristics. Based on the properties, two fundamental methods are introduced for fast evaluating schedules. FIG (Fast Iterative Greedy algorithm) is proposed for the considered problem, which includes initial solution generating and solution improvement phases. Besides an initial solution generating method being constructed, a segment based reconstructive heuristic and an iterative improvement procedure are developed for local and global search respectively to improve the current solution. FIG is compared with PH1p, SRTS and DPSOvnd algorithms on 110 traditional benchmark instances. Computational results show that FIG outperforms SRTS and PH1p but a little worse than DPSOvnd in effectiveness. In efficiency, FIG is better than SRTS and DPSOvnd but a little worse than PH1p