混合粒子群算法求解单机批调度问题.pdf

《混合粒子群算法求解单机批调度问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第１１期常俊林等．混合粒子群算法求解单机批调度问题１２４５混合粒子群算法求解单机批调度问题常俊林孟彦军王庆叶宾（中国矿业大学信息与电气工程学院，江苏徐州２２１００６）摘要设计了一种混合粒子群算法（ＨｙｂｒｉｄＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ，ＨＰＳＯ）以求解基于工件动态到达的最小化最大拖期时间单机批调度问题。该算法在标准粒子群算法的基础上引入了惯性权重正弦调整，以改善标准粒子群算法的收敛速度和全局收敛性，然后采用自适应变异全局极值算法增强粒子群优化算法跳出局部最优解的能力，防止算法陷入局部最优。应用改进的算法对实验设计问题进行求解，证明了改进算法的有效性。关键词单

2、机批调度粒子群算法惯性权重中图分类号ＴＨ７０１文献标识码Ａ文章编号１０００３９３２（２０１４）１１１２４５０６粒子群算法是通过模拟鸟群觅食行为而发展赖于种群规模，因此在解决大规模问题时收敛性起来的一种基于群体协作的随机搜索算法，该算能较差。文献［９］中微粒群算法在对批调度问题［１］法已在工业中有了广泛应用。求解时，主要是使用工件序列对解进行编码，将改单机调度是生产调度问题的一种特殊形式，进操作放在成批阶段，对微粒群算法得到的工件半导体芯片的预烧、电路测试、港口货物装卸及金序列?用动态规划算法进行改进。上述启发式方属加工等都属于该类型。在实际生产过程中，对法不能充分考虑问题的约

3、束条件，难以找到最优于大规模的生产活动，需要进行批量处理，机器在解，因此，另外一些学者采用了性能更优的元启发式算法（ｍｅｔａｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍ）。文献［１０］提出处理工件时，可以将多个工件同时进行加工以提了求解最小化最大完工时间的单机批处理调度问高生产效率，降低生产成本，这就是所谓的单机批题的启发式算法和蚁群算法，并且考虑了工件尺调度问题。文献［２］首先提出了该类问题的单机寸不等和动态工件到达的约束条件。文献［１１］器模型，即单机批调度问题，证明了该类问题的制利用蚁群聚类算法求解工件具有不同到达时间的造跨度问题是强ＮＰ问题。文献［３］求解极小化单机批调度问题。上

4、述算法虽然能在一定程度上总完工时间的单机批调度问题，提出了基于工件有效求得问题的优化解，但是随着迭代次数的增序列的蚁群算法和基于批序列的蚁群算法。文献加，算法容易陷入局部最优，降低算法的收敛速［４］研究了单机环境下工件尺寸有差异的批调度度。因此笔者提出利用混合粒子群算法来求解工问题，并设计了一种改进蚁群算法对问题的制造件动态到达的单机批调度问题，并引入自适应策跨度进行优化。文献［５］采用模拟退火方法求解略和惯性权重正弦函数，防止算法陷入局部最优，最小化最大完工时间的单机批处理调度问题。随同时也提高了算法的收敛速度。着单机批处理调度问题研究的深入，对于调度问１数学模型题的约束条件也越

5、来越多，工件动态到达的单机单机批调度问题描述如下：工件到达之后，在批调度问题的研究也己逐渐成为一个很有价值的满足机器容量Ｂ和工件到达时间的约束下，可ｍａｘ研究方向。但是目前研究工件动态到达的单机批以将多个工件作为一批同时进行加工，并且只有［６，７］调度的文献很少，并且在生产调度问题的优加工时间相同的工件才可以加入同一批中，同一化研究方面，应用智能优化算法来改进求解的质批工件具有相同的开始和结束加工时间。从一批量仍存在不足。文献［８］利用分批的启发式规则产生初始种群，然后重新设计了交叉算子和变异收稿日期：２０１４０９１９（修改稿）算子以优化制造跨度。但遗传算法的求解性能依基金项目

6、：国家自然科学基金资助项目（６１１０４０３９）１２４６化工自动化及仪表第４１卷开始加工直到该批加工完成，该过程不允许中断，ｗ———惯性权重因子。也不允许有工件中途退出或加入该批，因为同一２．２混合粒子群算法批中的工件由一台机器进行加工，具有共同速度，由于所求调度问题是离散的，所以采用基于所以批加工时间由批中工件的加工时间最大的工工件序列的编码方式可以更好地表达问题的解。件决定。到达时间、交货期都是已知的。为了保证编码策略不遗漏问题的全局最优解，并根据上述描述，所求问题的数学模型和约束使优化操作满足状态的可行性和合法性，设计一条件为：种针对随机键编码的基于升序排列（ｒａｎｋｅｄｏｒ

7、ｄｅｒｂＲ＝ｍａｘ｛ｒｊ｜ｊ∈ｂ｝（１）ｖａｌｕｅ，ＲＯＶ）的操作，用于实现从微粒的连续位置ｂｂｂＣ＝Ｐ＋Ｓ（２）矢量到工件排序的转换。假定有６个工件的调度ｂＬ＝Ｃ－ｄ（３）ｉｉ问题，设根据ＮＥＨ启发式算法和随机方法产生粒ｓ．ｔ．子位置［１．９，１．８，０．７，３．５，２．４，１．２］，采用ＲＯＶｂｂＳ≥Ｒ（４）规则，基于升序排列得：４，３，１，６，５，２，所得排列即ｎｂ≤Ｂｍａｘ（５）工件的加工序列。ｂＰ＝ｍａｘ｛ｐ｝（６）ｉ在式（８）中，由于粒子速度向量ｖ本身具