钢铁企业加工过程可分为炼铁区、炼钢区和轧线区。轧线区的生产工艺及管理的主要特点是物料以离散件(工件)的形式送入产线,物流呈交叉网状分布,部分产线具有高温特征,由于产线加工设备调整费用高,物料之间需要进行集批,经常以串联批的生产方式在产线上进行加工。这种以批生产方式为主的生产调度问题被称为批调度。轧线批调度问题是对于给定的被调度的工件集合确定批的组成和结构,以及在相应产线设备上的分配、排序和时间表的问题,是一类带有复杂约束的组合最优化问题。研究其建模与优化方法对于充分挖掘机组产能、提高生产效率、节能降耗、提高产品质量具有重要意义。钢铁企业的轧线生产主要覆盖热轧、酸轧、连续退火、电镀锌及彩涂等生产阶段,本文分别从不同的轧线生产阶段中提炼出如下的批调度问题：热轧并行产线的生产调度问题、冷轧连退产线钢卷生产排序问题、冷轧连退产线钢卷生产成组批调度问题、冷轧电镀锌产线钢卷排序问题、冷轧彩涂产线钢卷排序问题、轧线钢卷生产调度问题。针对上述不同的问题建立了相应的数学规划模型,并根据问题的特点分别开发了基于动态规划的多项式最优算法、基于列生成的最优化算法、基于禁忌搜索(TS)和过滤和扇(F&F)算法的智能优化算法,最后以连续退火产线为背景开发了批调度决策支持系统,论文主要工作如下：(1)以热轧生产阶段加工过程为背景,提炼出并行产线的生产调度问题。该问题在轧批的组成给定情况下(板坯链优先级约束),确定轧批在并行热轧产线上,即热轧阶段中的分配及排序,使得高温的板坯由于等待所引起的总的能源损失费用最小。该问题的特征是带有链式优先级约束、板坯动态到达、目标函数考虑能损特征。基于以上特征,当考虑能损量随板坯等待时间的变化呈线性关系时,该问题可归结为chains, rjk,hot|Σfjk(waitjk)。针对该问题的强NP-难求解特性,提出了分支定价算法,在分支树的每个节点提出列生成算法构造下界,针对列生成算法价格子问题采用常规动态规划算法求解复杂度高的难点,提出了基于状态空间松弛的动态规划算法,明显地提高了子问题求解效率。为了增强分支定价算法求解该类问题的通用性,进一步将该算法扩展到能损量随板坯等待时间的变化呈非线性关系的复杂情况。通过实验验证,无论对于线性能源损失函数还是非线性能源损失函数,提出算法均可在合理时间内最优求解中规模问题。(2)以连续退火生产线为背景,提炼出冷轧连退产线钢卷生产排序问题。该问题是确定钢卷在一个连退产线上的处理顺序,不仅需要考虑两个连续退火的钢卷之间的退火温度、宽度、厚度切换关系,尽量使总的生产切换费用最小；还需要考虑任意三个邻接钢卷之间的退火温度、宽度、厚度切换关系,使得切换趋势尽量平滑。通过将此问题归结为一类特殊的旅行商问题,建立了数学规划模型。针对此问题难于求解的特征,提出禁忌搜索算法进行近似求解。为了进一步改进算法性能,克服搜索过程易于陷入局部最优的缺点,提出了基于交替路径变换邻域的kick策略,构造了多项式动态规划算法搜索此邻域。基于实际数据的实验验证所提的基于禁忌搜索的算法在合理的计算时间内可有效的求解工业生产规模的算例。(3)以连续退火生产线为背景,提炼出冷轧连退产线钢卷生产成组批调度问题。该问题对于给定的钢卷簇,需要确定钢卷在一条连退产线上,簇的分批决策、加工顺序及调度时间表,其特征在于钢卷按簇的方式组织生产,不同簇之间存在大的调整时间和调整费用,同簇内的钢卷之间存在小的调整时间及调整费用。对于该问题当目标是最小化总的调整费用和提前拖期惩罚费时,建立了线性整数规划模型,开发了混合禁忌搜索和过滤和扇(F&F)算法的求解方法。在混合算法中,禁忌搜索算法用于产生初始解及产生候选移动,F&F算法通过搜索Filter-and-fan邻域树从候选移动中筛选构造出较好的组合移动。通过与CPLEX标准软件求解结果比较,验证了所提出的混合算法的有效性。(4)以电镀锌生产线为背景,提炼出冷轧电镀锌产线钢卷排序问题。该问题在满足相同后处理方式的钢卷连续从宽到窄进行加工(相同宽度的钢卷要求连续加工,称为簇)等实际生产约束的要求的情况下,确定一条电镀锌产线上,钢卷之间总切换费用最小的钢卷顺序。针对该问题建立了线性整数规划模型。基于对问题的最优解的结构特征和性质分析,开发了两阶段复杂度为O(nk3)的多项式算法对该问题进行最优求解。算法第一阶段对于一个簇边界钢卷给定情况下确定该簇内钢卷加工顺序。针对簇内钢卷加工顺序子问题,构造了多项式动态规划算法对其进行最优求解。算法第二阶段确定簇之间的加工顺序。针对簇间排序子问题,构造了簇边界钢卷为状态变量的动态规划递归方程,能够在多项式时间获得问题的最优解。为了满足一些实际工业问题的动态实时性要求,基于提出的最优解性质,开发了构造式启发式算法。通过实验表明了两阶段最优算法计算时间明显小于CPLEX获得最优解的时间；提出的启发式算法与最优解非常接近,运行时间稳定且平均运行速度快于两阶段最优算法。(5)以彩涂生产线为背景,提炼出单个加工单元钢卷排序问题和多个加工单元钢卷排序问题。这两个问题是在满足实际生产约束情况下,从候选钢卷中选择部分钢卷,分别构造一条彩涂产线上一个加工单元中切换费用最小的钢卷顺序和一条彩涂产线上多个加工单元中切换费用最小的钢卷顺序。问题特征在于彩涂生产线中两次换辊之间机组加工能力有限,钢卷集批生产,宽度、厚度、颜色切换等工艺约束,以及同时考虑普通卷和过渡卷的选择和排序。单个加工单元钢卷排序问题可归结为带容量约束的带选择奖惩的旅行商问题。针对单个加工单元钢卷排序问题中排序和选择耦合的特点,提出有效降低排序困难的统治规则,并构造伪多项式动态规划算法决策基于给定钢卷排序的最优钢卷选择方案。多个加工单元钢卷排序问题可归结为带选择惩罚的车辆调度问题。针对同时考虑多个加工单元的所引起的求解困难,开发了禁忌搜索算法,提出在每次迭代中搜索多个邻域获得组合移动的策略,克服了搜索单一邻域易于陷入局部最优的困难。为了评价所获得解的性能,提出列生成算法构造下界。经实验验证,禁忌搜索算法可快速获得近优解,列生成算法所获得的下界是紧的。(6)以存在无关并行生产线的酸轧生产阶段为背景,提炼出轧线钢卷生产调度问题。该问题决策钢卷在无关并行产线上的分配情况和加工顺序,其特征在于考虑无关并行产线、同时考虑总完成时间和总拖期两个优化目标。针对问题特征,建立了数学规划模型描述问题。针对多目标特性,提出基于理想点法的求解策略,其中,针对最小化完工时间的目标函数,建立线性规划模型描述问题,从而获得问题的理想点；针对最小化总拖期目标函数,提出基于局域搜索的启发式算法进行求解；综合以上结果,将考虑最小化完工时间的目标函数的理想点作为解的上界,将多目标函数转化为一个评价解与理想点接近程度的单目标问题,并提出局域搜索算法获得原问题非劣解,缩小了多目标问题求解的搜索范围。通过实验验证,算法可快速获得多目标问题非劣解。(7)针对轧线共性工艺特征,以具有典型复杂工艺约束的连续退火产线为背景,将上述连续退火产线钢卷排序问题模型及算法作为内核,开发了用于制定钢卷排序方案的决策支持系统。通过对实际数据的测试,验证算法和系统可有效求解钢卷排序问题。