钢铁工业是国民经济的重要支柱产业之一。近年来,随着建筑业、汽车制造业、造船业和家电业的大力发展,对钢材的需求数量和质量提出了更高的要求。由于钢铁生产具有多阶段、物件带有高温连续运作、物流呈交叉网状结构等特点,这就决定了物件在工序上的生产调度、连接工序之间的运输物流调度以及生产和物流调度的衔接都有严格的要求。合理进行生产和物流调度,有利于钢铁工业工序之间的物料紧凑衔接、减少中间等待时间,从而降低能耗、提高大型装置的设备利用率,达到降低生产和物流的综合成本、提高产品质量、提高钢铁工业竞争力的目的。本文以钢铁企业的高能耗的炼钢和初轧为背景,分别从这两个工序中提炼出具有热链物流特征的生产和运输调度问题,进行理论研究。基于复杂性分析、算法最坏情况分析、多项式时间算法、近似策略、动态规划等多种技术手段,主要研究三个方面的问题：具有恶化特征的生产调度问题、生产和运输协调调度问题、考虑恶化特征的生产运输协调调度问题。具体内容概括如下：1)具有恶化特征的生产调度问题研究(1)从钢锭在均热炉中加热的过程中提炼出工件带有释放时间和恶化特征的批处理机调度问题,其中工件在批处理机上的加工时间是工件在批处理机前的等待时间的一个分段函数,目标函数为最大完成时间的最小化。证明了该问题是NP-难问题。分别从相同的释放时间、批处理机能力无限以及工件具有优先次序三个方面,研究了三种特殊情况的多项式时间算法。(2)从模铸到均热的生产过程提炼出了并行机和批处理机两阶段生产的恶化调度问题,其中工件的恶化是指工件在批处理机上的加工时间与工件在两阶段之间的等待时间有关。目标函数既考虑了两阶段生产的机器利用率,又考虑了批处理机的空载惩罚,即为最大完成时间和批处理机空余的惩罚费用之和的最小化。对于这个问题,证明了强NP-难性,提出了一个启发式算法,理论上分析了算法的最坏情况性能,并通过数值仿真实验,验证了算法性能的有效性。2)生产和运输协调调度问题研究(1)从钢锭的运输以及均热的过程受到启发,提炼出了多个台车生产前运输与批处理机生产的协调调度问题。目标函数为工件总完成时间与批处理机启动费用之和的最小化。首先利用划分问题证明了该问题是NP-难的,通过动态规划提出的伪多项式时间算法证明了该问题是一般意义NP-难问题。最后提出了解决问题的全多项式时间近似策略。而当工件在台车上的分配给定时,通过动态规划给出了多项式时间的最优算法。(2)从模铸到均热的生产和运输中提炼出了二机之间带有运输考虑的二机流水调度问题,其中在运输的过程中考虑工件是否占有不同的物理空间两种情况。目标函数为最大完成时间的最小化。对于工件体积相同的情况,给出了最坏情况性能比为2的启发式算法。对于工件体积不相同的情况,给出了最坏情况性能比为7/3的启发式算法。(3)从均热到初轧的生产过程提炼出了带有阻滞和运输时间考虑的两阶段生产调度问题,工件先在第一阶段批处理机上进行生产,当第二阶段的单机有空闲时才可以运输到第二阶段进行生产,如果单机不可利用,则批处理机上形成了阻滞。目标函数既考虑了工件的最大完成时间,又考虑了工件在批处理机上的总阻滞时间。对于总的阻滞时间的最小化问题,给出了多项式时间的最优算法。对于最大完成时间最小化问题,给出了强NP-难的证明,提出最坏情况性能比为2的启发式算法,实验结果证明了算法的有效性。对于最大完成时间和总阻滞时间的线性组合最小化问题,提出了混合整数规划模型,给出了强NP-难的证明,提出了启发式算法,并且从理论分析与实验结果两个方面验证了算法的有效性。(4)从初轧生产到成品运输的过程提炼出了并行机生产与成品运输的协调调度问题。目标函数为工件总完成时间与运输费用之和的最小化。根据问题所满足的性质,通过过程划分及动态规划给出了解决问题的伪多项式时间算法,并且证明该问题是一般意义NP-难问题。对于工件在并行机上的分配给定的特殊情况,提出了多项式时间的最优算法。(5)从钢锭在均热炉加热的前后生产过程提炼出了批处理机上生产与生产前后两阶段运输的协调调度问题。目标函数为工件的最大完成时间与批处理机启动费用之和的最小化。提出了问题的混合整数规划模型,给出了强NP-难证明。并且提出了最坏情况性能比为2的启发式算法,实验结果证明了算法的有效性。对于工件的加工次序确定的情况,给出了多项式时间的最优算法。3)考虑恶化特征的生产运输协调调度问题研究从均热车间中提炼出了工件生产前的运输以及批处理机生产的协调调度问题,其中也考虑了工件在批处理机的生产的恶化特征,这里的恶化是指工件在批处理机上的加工时间是关于工件的暴露时间的分段函数。目标函数为最大完成时间和批处理机的启动费用之和的最小化。证明了问题的一般情况以及批的数量受限的情况都是强NP-难问题,给出了启发式算法,并且进行了最坏情况性能比分析,实验结果也验证的算法的有效性。对于工件的完成时间受限的情况,证明了该问题也是强NP-难问题。对于工件的加工顺序给定的情况,给出了多项式时间最优算法。