高效的优化方法对于工业生产调度有着重要的实际意义,但依据计算复杂性理论,大多数生产调度问题都属于强NP难问题,因而全局优化算法难以应用于复杂的实际生产调度问题。Lagrange松弛方法通过利用调度问题的可分离结构,采用分解与协调策略,能在可接受的时间范围内得到高质量的解,同时给出问题的下界(相对于最小化问题)以评价解的质量,因而被公认为是解决复杂调度问题的一个有效途径。Lagrange松弛方法利用Lagrange乘子松弛优化问题的特定耦合约束,将其引入到目标函数之中,从而得到一个与乘子对应的Lagrange松弛问题,一般通过次梯度算法求解Lagrange对偶问题得到最优乘子,从而得到原问题的下界。在次梯度算法的每次迭代中,需精确求解松弛问题得到次梯度来更新乘子,然后基于松弛问题的解,依据启发式方法构造一个可行解,同时保留最好的可行解作为原问题的解。然而,Lagrange松弛方法存在如下问题：(1)传统次梯度算法的收敛条件因过于严格而在实际应用中难以实现,导致人为设置终止条件,使得算法无法收敛到对偶问题最优值(即原问题下界)；(2)次梯度算法的震荡现象导致收敛速度慢；(3)次梯度算法因每次迭代都需精确求解松弛问题导致算法效率低。本文针对上述问题进行了优化理论的研究,提出了改进的Lagrange松弛方法,并将其应用于炼钢-连铸生产调度问题,取得的主要成果如下：1.针对传统次梯度算法的收敛条件因过于严格而难以实现的问题,通过引入Brannlund水平控制策略,提出了次梯度水平算法,给出了算法在无需问题特殊信息(如初始迭代点与最优点的距离)的条件下的可实现收敛条件,以及算法的收敛性和收敛率的分析与证明。本文将基于Brannlund水平控制策略的Lagrange松弛方法应用于炼钢-连铸生产静态调度问题。由于Lagrange松弛方法的求解质量和效率与问题的数学模型密切相关,因此,本文基于冶炼和精炼阶段的设备能力约束(不同炉次在同一设备上不能产生作业冲突)的松弛策略,研究了基于两种数学模型的求解方法：(1)建立了基于大M法的混合整数规划(Mixed Integer Programming, MIP)模型,给出了求解松弛问题的线性规划方法,针对迭代过程中存在无界松弛解的情况,给出了保证松弛解有界的充要条件,提出了避免无界的方法；(2)建立了基于时间索引变量的0-1整数规划(Integer Programming,IP)模型,考虑到连铸约束特点,分别提出了基于炉次单元、浇次单元和连铸机单元的三种松弛策略以及求解松弛问题的多项式动态规划方法。基于实际钢铁生产数据的仿真实验结果表明,基于IP模型方法的求解质量和效率优于基于MIP模型的方法；在基于IP模型的方法中,基于连铸机单元的松弛策略的求解质量最好,但基于炉次单元的松弛策略的求解效率最高。2.针对传统次梯度算法收敛速度慢的问题,通过分析两种造成收敛速度慢的震荡现象,引入条件-偏转次梯度,结合次梯度水平算法,提出了条件-偏转次梯度水平算法,给出了算法的收敛性和收敛率的分析与证明。基于经典问题的数值实验结果表明,条件-偏转次梯度次梯度水平算法显著地提高了Lagrange松弛方法的效率。针对带有不同精炼工序的(柔性作业型)炼钢-连铸生产调度问题,建立了基于时间索引变量的0-1整数规划模型,采用冶炼和精炼阶段的设备能力松弛策略,将基于条件-偏转次梯度水平算法的Lagrange松弛方法应用于炼钢-连铸生产调度问题。基于实际钢铁生产数据的仿真实验结果表明,条件-偏转次梯度水平算法显著地提高了Lagrange松弛方法求解炼钢-连铸生产调度问题的效率。3.针对传统次梯度算法因每次迭代都需精确求解松弛问题导致效率低的问题,通过引入近似次梯度,使其可以近似求解松弛问题,结合条件-偏转次梯度水平算法,提出了条件-偏转近似次梯度水平算法,称基于此算法的Lagrange松弛方法为Lagrange松弛水平方法,并给出了算法的收敛性和收敛率的证明,以及松弛问题的近似误差与对偶问题最优值之间的关系,为评估近似解提供了理论依据。本文将Lagrange松弛水平方法应用于加工时间可变的炼钢-连铸生产重调度问题。首先,基于时间索引变量,建立了适用于不同扰动的重调度问题的混合整数规划模型；其次,采用基于炉次和连铸机单元的松弛策略,提出了针对加工时间可变的松弛问题的多项式动态规划算法,在此基础上,进一步提出了误差可控的近似优化方法。基于实际钢铁生产数据的仿真实验结果表明,基于连铸机单元和炉次单元松弛策略的方法的求解质量差别很小,但前者的效率要略高于后者。此外,不同误差水平下的仿真实验结果表明,条件-偏转次梯度水平算法显著地提高了Lagrange松弛方法求解炼钢-连铸生产重调度问题的效率。