冶金工业是重要的原材料工业,也是国民经济的重要支柱产业。生产计划与调度是冶金工业生产运作管理的重要环节之一,合理有效地制定生产计划与调度才能使企业提高生产率、降低生产成本、提高产品质量、确保生产系统处于优化运行状态。因此,探讨适合冶金工业生产计划与调度问题的建模和优化方法已经成为近年来工业界和学术界的研究热点。本文以黑色金属钢铁生产和有色金属铝生产为背景,分别对冶金生产批量计划、带有不同冶金生产特征的生产调度以及生产批量计划与调度集成优化问题进行了建模和优化方法的研究。其研究有利于冶金企业资源优化配置、降低能源损耗、提高设备作业率、提高生产效率、提高客户服务水平,从而提高冶金企业核心竞争力。具体的研究内容概述如下：1)批量计划问题在钢铁企业生产中,批量计划是将客户的多品种小批量的需求组合成生产批,在满足客户多样性需求的同时,尽量使企业内部按照批量模式组织生产,达到经济运行的目的。炼钢生产阶段的批量计划称为炉次计划,它是将客户多样性需求的合同根据钢级和规格的要求组合成炼钢间歇生产设备所对应的基本生产单位-炉次的决策过程。针对炼钢生产阶段中的炉次批量计划问题,考虑符合炼钢生产的工艺约束和组合批条件的限制,对炉次批量计划问题建立了混合整数规划模型,并设计了两种基于拉格朗日松弛的求解方法。在第一种拉格朗日方法中,通过松弛分配约束得到的拉格朗日松弛问题,进一步分解获得的子问题用动态规划最优求解；在第二种拉格朗日方法中采用了变量分离技术。大量随机实例测试的结果表明,两种拉格朗日松弛算法都能获得较好的平均对偶间隙,基于变量分离的拉格朗日松弛方法稍好于第一种方法。2)生产调度问题(1)带有释放时间的单机调度问题针对带有释放时间的单机调度问题,采用基于时间槽的思想建立了一个混合整数线性规划模型。基于这种连续时间建模的方式,将此问题转化为分配和时间表决策问题,其主要的决策变量为工件与时间槽的匹配以及时间槽的开始和结束加工时间。针对此模型,提出了拉格朗日松弛算法进行求解。将释放时间约束和工件优先级约束松弛,通过分解获得两个子问题：一个子问题可直接通过分析变量的系数获得最优解；而另一个子问题可以归结为分配问题,利用匈牙利算法获得最优解。实验结果表明基于拉格朗日的启发式算法得到的上界接近于CPLEX得到的最优目标函数值。(2)带有恶化工件的单机调度问题在钢铁企业中,如果高温的工件在加工前等待,势必将引起温降,而重新加热使其满足温度要求又必将导致加工时间的增加,这种工件处理时间依赖开始时间或等待时间的特征被称为恶化。针对这类带有恶化性质工件的单机调度问题建立了一个混合整数规划模型,并设计了拉格朗日松弛算法对其进行近似求解。在松弛方法中,通过松弛机器能力约束,使得到的松弛问题可以分解为工件级子问题,并提出一种缩短时域的策略加快拉格朗日松弛算法的求解速度。大量随机实例测试的结果显示,这种算法的平均对偶间隙为1.28%,算法的平均运行时间为20.89秒,表明所提出的算法能在较短的运行时间内得到问题的近优解。(3)可重入混合流水车间调度问题在铝的冷轧生产阶段,铝卷通常需要多次进入冷轧工序进行加工(反复地在同一工序进行加工)以达到表面质量和机械性能的工艺要求,这种特征被称为可重入。针对可重入混合流水车间调度问题,建立了一个混合整数规划模型,并设计了拉格朗日松弛算法。为了克服常规的拉格朗日松弛算法在每次迭代中必须最优求解全部子问题而导致算法效率低的缺点,提出了基于代理次梯度的拉格朗日松弛算法,使得算法在每次迭代中只需要最优求解一个通过能力松弛后分解得到的工件级子问题。实验结果表明对于小规模问题所提出的算法能够在相对较短的时间内有效地求解该问题。(4)带释放时间的动态并行机调度问题在钢铁企业的炼钢连铸阶段,由于生产环境常常会受到多种不确定性或随机性因素的影响,静态生产调度必须进行调整才能适应动态环境变化的要求。本文针对工件的释放时间与加工时间动态变化的并行机调度问题,基于模型预测控制原理,建立了带有滚动时域的混合整数规划模型,模型的目标函数考虑了总权重完成时间、能耗以及重调度与初始调度的偏差。对应于滚动时域的每个窗口的调度子问题,设计了拉格朗日松弛算法进行近似求解。大量随机实例测试的结果表明基于模型预测控制的滚动时域建模思想和拉格朗日松弛方法所得到的解优于基于人工经验的被动调整方法,平均改进量为11.72%。3)批调度问题(1)带恶化工件的并行机批调度问题在钢铁热轧生产阶段,为了节省调整费用,板坯需要组合成批进行轧制。组合成批的板坯如果在轧制前等待,将引起温降。当温度低于轧制的入口温度时,板坯必须重新加热,从而导致加工时间的增加。本文针对工件带有恶化性质的并行机批调度问题,分析了最优解性质,并基于解的性质,提出了改进的分散搜索算法求解该问题。为了评价改进分散搜索算法的性能,采用拉格朗日松弛算法构造了问题的下界。大量随机实例的测试结果表明,提出的改进算法所得到的解与下界之间的平均偏差在2%以内。(2)铝锭生产的集成批量计划与调度问题从铝锭的熔炼和铸造的两阶段生产中,提炼出一类集成生产批量与调度问题,该问题特点是同时决策批的组成、批的大小、批的分配以及批的排序和调度。针对铝锭生产集成批调度问题,建立了一个混合整数线性规划模型。考虑集成问题模型复杂难于求解的特点,设计了基于阶段分解和基于层次分解的两种启发式算法对问题进行求解。实验证明,两种启发式算法与CPLEX求解结果相比,在相对短的时间内均能得到较好的解,基于层次分解的启发式算法比基于阶段分解的启发式算法效果稍好。