常俊林 孟彦军 王 庆 叶 宾

(中国矿业大学信息与电气工程学院，江苏 徐州 221006)

粒子群算法是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法，该算法已在工业中有了广泛应用[1]。

单机调度是生产调度问题的一种特殊形式，半导体芯片的预烧、电路测试、港口货物装卸及金属加工等都属于该类型。在实际生产过程中，对于大规模的生产活动，需要进行批量处理，机器在处理工件时，可以将多个工件同时进行加工以提高生产效率，降低生产成本，这就是所谓的单机批调度问题。文献[2]首先提出了该类问题的单机器模型，即单机批调度问题，证明了该类问题的制造跨度问题是强NP问题。文献[3]求解极小化总完工时间的单机批调度问题，提出了基于工件序列的蚁群算法和基于批序列的蚁群算法。文献[4]研究了单机环境下工件尺寸有差异的批调度问题，并设计了一种改进蚁群算法对问题的制造跨度进行优化。文献[5]采用模拟退火方法求解最小化最大完工时间的单机批处理调度问题。随着单机批处理调度问题研究的深入,对于调度问题的约束条件也越来越多，工件动态到达的单机批调度问题的研究也己逐渐成为一个很有价值的研究方向。但是目前研究工件动态到达的单机批调度的文献很少[6，7]，并且在生产调度问题的优化研究方面，应用智能优化算法来改进求解的质量仍存在不足。文献[8]利用分批的启发式规则产生初始种群，然后重新设计了交叉算子和变异算子以优化制造跨度。……