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

被引：8

作者：

朱夏

李小平

王茜

机构：

[1] 东南大学计算机科学与工程学院

[2] 计算机网络和信息集成教育部重点实验室

来源：

计算机学报 | 2009年 / 32卷 / 01期

关键词：

无等待流水调度; 目标增量; 启发式算法; 总完工时间最小;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

最小化总完工时间无等待流水调度是典型的NP-完全问题,广泛存在于实际生产系统.改变传统求解调度序列目标函数的模式,提出目标增量法,通过目标函数变化量判断新解的优劣,大大降低算法所需计算时间;通过证明启发式算法基本操作的目标增量性质,设计两种基本目标增量法以快速评估新产生解的质量.提出快速迭代贪婪算法FIG(Fast Iterative Greedy algorithm)求解该问题,构造初始解生成算法,提出分段式重构局部搜索方法和迭代改进全局搜索策略以进一步提高解的质量.基于110个经典Benchmark实例,将提出的FIG算法与目前求解该问题较好的启发式算法PH1p和元启发式算法SRTS、DPSOvnd进行比较,实验结果表明FIG在性能上优于SRTS和PH1p,略逊于DPSOvnd;在效率上优于SRTS和DPSOvnd,略逊于PH1p.

引用

页码：132 / 141

页数：10

共 5 条

[1] New heuristics for m-machine no-wait flowshop to minimize total completion time [J].

Aldowaisan, T ;

Allahverdi, A .

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2004, 32 (05) :345-352

[2]

Heuristic algorithm for scheduling in the no-wait flow-shop[J] . Edy Bertolissi.Journal of Materials Processing Tech. . 2000 (1)

[3] Genetic algorithms applied to the continuous flow shop problem [J].

Chen, CL ;

Neppalli, RV ;

Aljaber, N .

COMPUTERS & INDUSTRIAL ENGINEERING, 1996, 30 (04) :919-929

[4]

Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling[J] . B. L. MacCarthy,Jiyin Liu.International Journal of Production Research . 1993 (1)

[5] HEURISTICS FOR FLOWSHOP SCHEDULING [J].

KING, JR ;

SPACHIS, AS .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 1980, 18 (03) :345-357

← 1 →