最小化总完工时间的流水作业调度混合算法

被引：10

作者：

齐学梅 ^{[1
,2
]}

李小平 ^{[1
,3
]}

王茜 ^{[1
,3
]}

机构：

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

[2] 安徽师范大学数学计算机科学学院

[3] 东南大学计算机网络和信息集成教育部重点实验室

来源：

东南大学学报(自然科学版) | 2008年 / 38卷 / 06期

基金：

国家高技术研究发展计划(863计划);

关键词：

流水作业调度; 启发式算法; 禁忌搜索; 总完工时间;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

080201 [机械制造及其自动化];

摘要：

针对有效求解NP难的总完工时间最小流水作业调度问题,提出了一个有效的混合启发式算法产生初始解,并使用禁忌搜索算法对初始解邻域进行搜索的算法框架.基于不同的启发式算法,获得了3个混合禁忌搜索算法HA1,HA2和HA3.使用Taillards基准程序随机产生的大量实例,进行模拟实验,结果表明,所提出的3个算法通过扩大搜索范围提高了解的质量,在性能上均优于目前最有效的启发式算法.与目前最有效的算法相比,产生最好解的平均百分比偏差均下降至少30%,最优解所占比例皆有显著提高.

引用

页码：960 / 964

页数：5

共 6 条

[1]

An efficient constructive heuristic for flowtime minimisation in permutation flow shops [J].

Framinan, JM ;

Leisten, R .

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2003, 31 (04) :311-317

[2]

New heuristics to minimize total completion time in m-machine flowshops [J].

Allahverdi, A ;

Aldowaisan, T .

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2002, 77 (01) :71-83

[3]

Constructive and composite heuristic solutions to the P //∑ C i scheduling problem.[J].Jiyin Liu;Colin R Reeves.European Journal of Operational Research.2001, 2

[4]

A tabu search approach for the flow shop scheduling problem [J].

Ben-Daya, M ;

Al-Fawzan, M .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1998, 109 (01) :88-95

[5]

A heuristic algorithm for mean flowtime objective in flowshop scheduling [J].

Woo, HS ;

Yim, DS .

COMPUTERS & OPERATIONS RESEARCH, 1998, 25 (03) :175-182

[6]

An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs [J].

Rajendran, C ;

Ziegler, H .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1997, 103 (01) :129-138

← 1 →