物料需求计划(Material Requirements Planning, MRP)是制造资源计划/企业资源计戈(?)J(Manufacturing Resource Planning/Enterprise Resource Planning, MRPII/ERP)的基础,同时也是供应链管理(Supply Chain Management, SCM)的基础。在制造和分销企业中,遇到的最普遍的决策问题就是与MRP相关联的决策问题。虽然这些决策问题是这些企业每天都要面对的问题,但是并不意味着这些问题就是容易解决的。MRP是制造系统中协调产成品(由半成品和部件组成)补充决策的方法。MRP确保了在恰当的时间点制造系统中各个层次上的组件都具有足够的数量,使顾客对产成品的需求可以得到满足。由于组件数量的大小直接影响了生产系统的性能和生产力,而生产力是制造企业在市场中保持竞争力的重要因素,因此生产批量计划问题是MRP系统中的关键问题。由于MRP只能提供生产批量计划问题的可行解,因此寻找高质量解(具有最小成本的补充数量)的问题随之而来。实践证明当现实中的产品由几百个部件组成时,这个问题是一个棘手的组合优化问题。在生产批量计划问题的早期工作中,大部分研究集中于特定环境下的最优解算法。然而,只有较小规模的问题可以在合理的时间内得到最优解。随着问题规模的增加,所需要的计算量(更不用说它们的复杂性)也极度增加。这种情况促使人们需要开发大量的求解算法,使得计算时间和成本效益能够令人满意地得到平衡。生产批量计划问题可以分为多种类型。从生产能力来看,包括有资源约束和无资源约束批量计划问题；从产品的结构角度看包括单级结构、线型结构、装配结构和一般结构的批量计划问题；还有以需求方式角度来划分的固定需求、时变需求、随机需求和模糊需求环境下的批量计划问题等。由于生产批量计划问题起源于20世纪50年代,至今为止,关于生产批量计划问题模型方面的研究已经十分成熟,因此本文主要针对确定需求环境下具有不同生产结构的生产批量计划问题的求解算法进行了研究,设计了几种亚启发式(Meta-heuristic)算法。本文的主要工作包括：(1)对生产批量计划问题的相关研究进行了综述。介绍了生产批量计划问题的产生背景和概况,阐述了具有不同产品结构的生产批量计划问题的各种模型,概述了可以用于求解生产批量计划问题的相关亚启发式算法。(2)提出了可求解无资源约束多级生产批量(Multilevel Lot-sizing, MLLS)问题的粒子群优化(Hybrid Particle Swarm Optimization, HPSO)算法。传统的PSO算法是在具有连续定义域的实优化问题中寻优的有效工具,通过将传统PSO算法中粒子的速度和位置、加法、乘法等运算规则进行了重新定义,使得PSO算法能够求解具有二进制变量的MLLS问题,扩展了PSO算法的应用领域。在此基础上,对二进制版本的HPSO算法进行调整和变化,引入柔性惯量和反捕食概念,形成带有柔性惯量的PSO算法和带柔性惯量的反捕食PSO算法。通过计算算例表明了几种PSO算法对MLLS问题进行求解的可行性和有效性。(3)针对无资源约束MLLS问题,为避免基本遗传算法(Genetic Algorithm, GA)因过早收敛造成搜索效率低的问题,将排斥算子(Repulsion Operator, RO)概念引入GA中,提出带排斥算子的遗传算法(Genetic Algorithm integrated with RO, RGA)。采用RGA与GA对MLLS问题进行求解比较,结果表明RGA的运行效果优于GA。(4)分散搜索(Scatter Search, SS)算法是一种亚启发式算法,其应用范围已涉及优化领域中的许多NP难问题。本文提出结合变异算子的混合SS (Hybrid Scatter Search,HSS)算法对无资源约束MLLS问题进行了求解。计算实验表明HSS算法能够有效地求解MLLS问题,其求解结果明显优于GA的求解结果。(5)对上述三类算法采用英文文献中的benchmark算例进行求解性能比较分析。通过96个小规模问题,3个中规模问题和1个大规模问题的比较结果来看,SS算法在求解小规模和中规模问题时性能优于HPSO算法和RGA算法,在求解大规模问题时HPSO算法的性能更好。(6)将目前约束处理时常用的罚函数法和能力调整法与元算法相结合,提出了求解单级多产品多资源约束生产批量计划问题的混合元算法。采用3组算法执行策略,并对每组执行策略的具体实现过程以流程图的方式进行了描述。通过文献中的实例对3种执行策略进行了测试和比较,验证了算法的可行性和适用性。(7)针对多级多资源有资源约束的MLLS问题,提出了一种基于SS算法与能力调整方法相结合的方法(Scatter Search integrated with Capacity Adjustment Methods, CAM-SS),阐明了该方法的具体实现过程。在CAM-SS方法中,首先按无资源约束问题采用SS算法对问题进行求解；之后采用能力调整方法按“先顺序—后逆序”的方式逐个时段处理资源约束条件。通过对计算实例进行计算和结果比较分析,表明该算法在寻优能力、求解速度和稳定性方面明显优于文献中的GA算法。