摘 要：研究工件具有动态到达时间的热处理车间调度，建立以极小化工件等待时间期望为调度目标的批调度模型，并利用粒子群算法对模型进行求解。为验证算法的有效性，将其与蚁群算法、先到先加工规则（FCFS）下的算法进行比较。仿真结果表明，粒子群算法的结果最优。
　　关键词：动态到达；批调度；等待时间；粒子群算法
　　1 引言
　　Uzsoy[1]首先提出了批调度问题的单机器模型，即差异工件单机批调度问题（NSBM），证明了该问题为强NP难。赵玉芳等[2]均以Cmax为优化目标进行了相关性质的研究。徐瑞等[3]研究了单台机器优化目标为总完工时间的批调度模型。
　　然而，工件动态到达热处理车间后，很难直接进入热处理炉进行热加工，而是等待上一批次工件加工完成，这就会导致工件在热处理车间产生等待时间。等待时间过长，不仅会直接增加热处理车间的存储费用，占用大量存贮空间，而且会直接影响后续机加或装配车间的需求。然而，国内外关于热处理车间工件等待时间的调度优化模型鲜见，本文建立了单机环境下考虑工件动态到达，极小化工件等待时间期望的热处理批调度模型。若将工件等待时间期望记为W，此调度模型可表示为W-NSBM。
　　2 工件动态到达时间下的W-NSBM模型与算法编码
　　2.1 W-NSBM问题描述：
　　2.2 W-NBSM数学模型
　　根据以上假设，建立W-NBSM数学模型：
　　2.3 粒子群算法编码
　　3 仿真实验
　　采用随机产生数据的方法获得算例[5]，算例划分标准为：
　　结果分析：①算法方面，可以看到改进编码后的PSO算法在解决24种算例最小化工件等待时间这一问题上是优于其他的三种算法的。这说明了， PSO算法能够较好的应用于大规模和小规模工件数下工件等待时间的优化问题。②调度结果方面，无论工件数量的多少，工件在具有相同的到达时间和工件尺寸的条件下，工件加工时间长的工件等待时间期望高于加工时间短的工件。从而，我们可以得到一般结论：工件的加工时间越短，工件等待时间的期望越小。在趋于小规模工件数的情况下，大尺寸工件的等待时间期望优于小尺寸工件，在趋于大规模工件数的情况下，小尺寸工件的等待时间期望优于大尺寸工件。
　　4 结束语
　　本文考虑工件动态到达下极小化等待时间的热处理车间调度问题。设计了按照工件到达时间的微粒编码方式。仿真结果表明，在求解此类问题时PSO算法优于ACO和FCFS算法。
　　参考文献
　　[1]Uzsoy R. Scheduling a single batch processing machine with non-identical job sizes[J]. International Journal of Production Research，1994，32（7）：1615-1635.
　　[2]赵玉芳，唐立新.极小化最大完工时间的单机连续型批调度问题[J].自动化学报， 2006， 32（5）：730-737.
　　[3]徐瑞，陈华平，邵浩.极小化总完工时间批调度问题的两种蚁群算法[J].计算机集成制造系统，2010，16（6）：1255-1264.
　　[4]程八一，陈华平，王栓狮.基于微粒群算法的单机不同尺寸工件批调度问题求解[J].中国管理科学，2008，16（3）：84-88.
　　[5]吴超超，顾幸生.最优公共交货期单机提前/拖期调度和对应的批次送货[J].华东理工大学学报，2004，30（2）：211-215.