基于MMAS算法的带到达时间批调度问题研究

被引：6

作者：

许瑞 ^{[1
]}

陈华平 ^{[1
]}

朱俊红 ^{[2
]}

机构：

[1] 中国科学技术大学管理学院

[2] 合肥工业大学管理学院

来源：

系统工程学报 | 2011年 / 26卷 / 04期

关键词：

批调度; 到达时间; 最大完工时间; 蚁群算法; 最大-最小蚂蚁系统;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

研究了工件带到达时间的目标为极小最大完工时间(Cmax)的单机批调度问题,采用最大-最小蚂蚁系统（max-min ant system,MMAS）进行求解。针对问题带到达时间以及分批的特性,提出了两种候选列表（candidate list）构建批序列,有效地缩小了搜索空间的维度;考虑两种候选列表的工件对构造解具有不同的影响,针对不同的候选列表设计了相应的启发式信息.仿真实验部分从求解质量和时间性能两方面比较了本文提出的算法和标准的蚂蚁系统（ant system,AS）算法以及使用不同候选列表的MMAS算法.结果表明,本文的算法在质量和时间两方面均全面优于标准的AS算法,而提出的候选列表使得该算法在大幅度提高时间性能的同时,仍然能够取得近似最优解,从而在求解质量和时间性能两方面取得平衡.

引用

页码：474 / 484

页数：11

共 15 条

[1] 蚁群算法在卫星数传调度问题中的应用 [J].

陈祥国 ;

武小悦 .

系统工程学报, 2009, 24 (04) :451-456+488

[2] 并行分批排序问题综述 [J].

张玉忠 ;

曹志刚 .

数学进展, 2008, (04) :392-408

[3] 基于微粒群算法的单机不同尺寸工件批调度问题求解 [J].

程八一 ;

陈华平 ;

王栓狮 .

中国管理科学, 2008, (03) :84-88

[4] 基于蚁群优化算法的0-1背包问题求解 [J].

胡小兵 ;

黄席樾 .

系统工程学报, 2005, (05) :76-79+85

[5] 带到达时间分批排序问题的数学模型 [J].

姜冠成 .

苏州大学学报(自然科学版), 2005, (02) :22-27

[6] A hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem [J].

Fuh-Der Chou ;

Pei-Chann Chang ;

Hui-Mei Wang .

The International Journal of Advanced Manufacturing Technology, 2006, 31 :350-359

[7] Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms [J].

Damodaran, Purushothaman ;

Manjeshwar, Praveen Kumar ;

Srihari, Krishnaswami .

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2006, 103 (02) :882-891

[8]

A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor[J] . M. Mathirajan,A.I. Sivakumar.The International Journal of Advanced Manufacturing Technology . 2006 (9)

[9] Scheduling a batch processing machine with non-identical job sizes [J].

Azizoglu, M ;

Webster, S .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2000, 38 (10) :2173-2184

[10]

MAX – MIN Ant System[J] . Thomas Stützle,Holger H. Hoos.Future Generation Computer Systems . 2000 (8)

← 1 2 →