具有不同到达时间的差异工件批调度问题的蚁群聚类算法

被引：6

作者：

杜冰

陈华平

邵浩

许瑞

李小林

机构：

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

来源：

系统工程理论与实践 | 2010年 / 30卷 / 09期

关键词：

调度; 批处理机; 聚类; 蚁群算法; 组合优化;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

研究具有不同到达时间的差异工件在单机环境下的批调度问题.通过引入工件单元的概念并对分批约束进行松弛,提出了该问题的一个新的下界,证明了该下界的有效性.将蚁群算法和聚类算法相结合,提出了一种基于多阶段聚类的蚁群聚类算法ACC(Ant colony clustering).算法首先利用K-均值聚类将工件分簇,在簇内部通过蚁群算法搜索分批,最后提出一个全局优化算法对局部分批结果进行合成和优化.克服了蚁群算法随着工件规模增大求解时间过长的问题,适合于求解大规模算例.实验结果表明:与现有的启发式规则LPTBFF(Longest processing time & batchfirst fit)和HGA(Hybrid Genetic algorithm)算法相比,该算法求解效果更好.

引用

页码：1701 / 1709

页数：9

共 10 条

[1] 模糊制造系统中的不同尺寸工件单机批调度优化 [J].

程八一 ;

陈华平 ;

王栓狮 .

计算机集成制造系统, 2008, (07) :1322-1328

[2] 极小化完工时间和的有界批调度问题(英文) [J].

李曙光 ;

李国君 ;

赵洪銮 .

应用数学, 2006, (02) :446-454

[3] 蚁群算法在生产调度中的应用 [J].

姜桦 ;

李莉 ;

乔非 ;

吴启迪 .

计算机工程, 2005, (05) :76-78+101

[4] Flow shop问题的蚁群优化调度方法 [J].

王笑蓉 ;

吴铁军 .

系统工程理论与实践, 2003, (05) :65-71

[5] 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

[6] 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

[7] Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes [J].

Kashan, A. H. ;

Karimi, B. ;

Jolai, F. .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2006, 44 (12) :2337-2360

[8]

Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure[J] . Lionel Dupont,Clarisse Dhaenens-Flipo.Computers and Operations Research . 2002 (7)

[9] SCHEDULING A SINGLE BATCH PROCESSING MACHINE WITH NONIDENTICAL JOB SIZES [J].

UZSOY, R .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 1994, 32 (07) :1615-1635

[10]

Distributed optimization by ant colonies. Colorni A, Dorigo M, Maniezzo V. Proceedings of the First European Conference on Artificial Life . 1991

← 1 →