PDF《求解不相关并行机混合流水线调度问题的人工蜂群算法》

第29 卷第

12 期2012 年12 月控制理论与应用Control Theory &

Applications Vol.

29 No.

12 Dec.

2012 求求求解 解 解不 不 不相 相 相关 关 关并 并 并行 行 行机 机 机混 混 混合 合 合流 流 流水 水 水线 线 线调 调 调度 度 度问 问 问题 题 题的 的 的人 人 人工 工 工蜂 蜂 蜂群 群 群算 算 算法 法法文文文章 章 章编 编 编号 号号: 1000?8152(2012)12?1551?07 王凌, 周刚, 许烨, 王圣尧 (清华大学 自动化系, 北京 100084) 摘要: 针对不相关并行机混合流水线调度问题的特点, 设计了一种基于排列的编码和解码方法, 提出了一种有效 的人工蜂群算法. 在引领蜂和跟随蜂搜索阶段采用3种有效的邻域搜索方法, 以丰富搜索行为;

在侦察蜂搜索阶段 通过随机搜索对种群进行更新, 以增强种群多样性. 同时, 通过试验设计方法对算法的参数设置进行了分析, 给出指 导性参数组合. 通过基于典型实例的数值仿真以及与已有代表性算法的比较, 验证了所提算法的有效性和鲁棒性. 关键词: 混合流水线调度;

不相关并行机;

人工蜂群算法;

实验设计 中图分类号: TP18 文献标识码: A An arti?cial bee colony algorithm for solving hybrid ?ow-shop scheduling problem with unrelated parallel machines WANG Ling, ZHOU Gang, XU Ye, WANG Sheng-yao (Department of Automation, Tsinghua University, Beijing 100084, China) Abstract: According to the characteristics of the hybrid ?ow-shop scheduling problem with unrelated parallel machines (HFSPCUPM), we design a permutation-based method for encoding and decoding, and propose an effective arti?cial bee colony (ABC) algorithm. At the employed bee phase and the onlooker bee phase, three effective neighbor-search ap- proaches are used to enrich the searching behavior;

at the scout bee phase, the population is updated by using random search to enhance the diversity of population. Based on Taguchi method for experiment design (DOE), the effect from the parameter-setting is investigated and suitable parameter values are suggested. Numerical simulation based on bench- mark examples and comparisons with the existing typical algorithms demonstrate the effectiveness and robustness of the proposed algorithm. Key words: hybrid ?ow-shop scheduling;

unrelated parallel machine;

arti?cial bee colony;

design of experiment

1 引引引言 言言(Introduction) 混合流水线调度问题(hybrid ?ow-shop schedul- ing problem, HFSP)[1C2] 具有很强的应用背景, 广泛存 在于化工、 冶金、 纺织、 机械、 半导体、 物流等领域, 大量制造与服务问题均可归结为HFSP. HFSP整体 上具有流水作业特征, 同时某些工序上存在并行机 加工的特点, 求解难度大, 属于非确定性多项式(non- deterministic polynomial hard, NP-hard)问题. 因此, HFSP的研究具有重要的学术意义和应用价值. HFSP按照并行机类型分为3类: 相同并行机混合 流水线[3] , 即每阶段上工件在任一台并行机上的加 工时间相同;

均匀并行机混合流水线[4] , 即每阶段上 工件在任一台并行机上的加工时间与该台机器的加 工速度成反比;

不相关并行机混合流水线[5] , 即每阶 段上工件在任两台并行机上的加工时间互不相关, 取决于工件与机器的匹配程度. HFSP的求解方法早期主要包括精确算法[6] 和 启发式方法[7] . 精确算法在理论上能得到最优 解, 但计算时间通常难以接受, 一般只适于解决 小规模问题. 启发式方法可在较短时间内快速构 造解, 但难以保证解的质量. 近年来, 许多智能方 法被应用于HFSP, 譬如遗传算法(genetic algorithm, GA)[8] 、 模拟退火[9] 、 禁忌搜索[10] 、 蚁群算法[11] 、 微 粒群优化[12] 、 人工免疫系统(arti?cial immune sys- tem, AIS)[13] 等. 人工蜂群算法(arti?cial bee colony, ABC)[14] 是一种模仿蜜蜂觅食的群智能算法, 已被广 泛用于连续和组合优化问题, 如约束优化[15] 、 聚类 问题[16] 等. 在调度方面, Pan等[17] 针对批量流水线调度提出 了一种基于自适应搜索策略的离散人工蜂群算法, 使用排列编码并采用插入和交换等操作实现离散 空间的搜索;