约束满足混合算法求解提前/拖期Job Shop调度问题

被引：5

作者：

李俊芳

李铁克

王伟玲

机构：

[1] 北京科技大学经济管理学院

来源：

计算机工程与应用 | 2010年 / 46卷 / 16期

关键词：

约束满足; 提前/拖期; Job Shop; 禁忌搜索; 关键路径;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

针对提前/拖期Job Shop调度问题,建立其约束满足优化问题模型,提出了一种约束满足与禁忌搜索结合的混合算法。该算法基于约束满足思想,通过约束传播技术和启发式修复算法,得到可行调度作为禁忌搜索算法的初始解;再进行关键路径上的邻域变换,优化当前解;并采用一种全局邻域交换策略,扩大搜索空间,改善优化结果。数据实验表明了该混合算法的可行性和有效性。

引用

页码：12 / 15

页数：4

共 6 条

[1] 求解作业车间调度问题的全局邻域搜索方法 [J].

崔健双 ;

李铁克 .

计算机集成制造系统, 2009, 15 (07) :1383-1388

[2] 具有滚动优化特性的改进型蚁群算法及其在提前/拖期Job Shop问题中的应用 [J].

张晴 ;

陈知美 ;

顾幸生 .

华东理工大学学报(自然科学版), 2008, (01) :112-116

[3] Job-shop提前/拖期调度问题的研究 [J].

姚伟力 ;

杨德礼 ;

胡祥培 .

控制与决策, 2000, (03) :322-324+332

[4] 以JIT准时化为目标的Job-Shop遗传调度算法 [J].

王志杰 ;

晏平 ;

赵象元 ;

刘飞 .

系统工程理论方法应用, 1999, (02)

[5]

Constraint propagation techniques for the disjunctive scheduling problem[J] . Ulrich Dorndorf,Erwin Pesch,Toàn Phan-Huy.Artificial Intelligence . 2000 (1)

[6] A fast taboo search algorithm for the job shop problem [J].

Nowicki, E ;

Smutnicki, C .

MANAGEMENT SCIENCE, 1996, 42 (06) :797-813

← 1 →