生产调度是一类重要的组合优化问题,在工业生产、制造系统等领域应用广泛。合理的调度方案有助于提高生产效率,减少生产成本,因此对调度问题研究有着重要的现实意义。批调度是调度问题的一个重要分支。不同于经典调度问题,在批调度模型中,一台机器可以同时处理多个工件。差异工件批调度问题(Batch Processing Machines with Non-identical Job Sizes,NSBM)是对传统批调度问题的进一步扩展,即工件尺寸不同,且同一批中工件的总尺寸不能超过批的容量限制。邻域搜索算法是求解组合优化问题的一类重要优化方法,这类算法以进化的方式在解空间中进行寻优,具有简单、适用范围广和鲁棒性强等。本文将一种新的邻域搜索算法——自由搜索算法(Free Search,FS)应用于NSBM问题,主要工作如下:首先,充分利用工件序列这一启发信息求解NSBM问题,即首先采用FS算法寻找一个较优的工件序列,然后将该工件序列按一定的启发式规则进行分批。论文针对生产调度问题的离散性,设计了向量形式的编码方式,并结合改进的Best-Fit启发式分批规则,构造了工件序列编码的自由搜索算法。根据本文的目标函数,对算法模型中的信息素重新定义,并设置三类不同数值的邻域半径,避免算法陷入局部最优。实验表明,FS的求解效果优于现有的启发式算法和智能算法。其次,利用批序列的编码方式求解NSBM问题,即直接构造批,然后用邻域搜索算法对批序列优化。工件序列编码的方法在求解问题时结果会受到所选用的启发式分批规则的影响,若分批规则求解效果不好,则工件序列优化对结果的改进也很有限,且该方法不能在完备的解空间中寻优,不利于找到更好的解。论文提出了一种混合邻域搜索算法(Hybrid Neighborhood Search,HNS),根据FS算法在搜索过程中存在的停滞问题,加入差异演化算法和局部优化策略,并利用尖点灾变理论的精英保留机制进一步提高搜索效率,仿真实验验证了HNS算法的有效性。最后,对全文进行了总结,讨论了进一步的研究方向和设想。