本文针对从钢铁实际生产与物流管理过程中提炼出一类新型生产与物流批调度问题进行理论方法研究。从理论视角来看,该研究丰富了传统调度问题的理论研究,扩展了调度研究方法;从应用视角来看,对于流程工业,该研究在减少生产与物流成本、提高生产与物流设备利用率,以及降低能源和资源消耗方面具有重要的实际意义。本文针对生产批调度、物流批调度、生产与物流协调批调度等生产与物流调度问题,从计算复杂性、问题模型和解的结构特征、算法设计及性能分析等方面进行了系统的理论分析。在分析问题复杂性的基础上,对于可解问题,构造多项式时间最优算法。对于一般意义NP-难问题,构造伪多项式时间动态规划算法。对于强NP-难问题,研究其最优解性质,构造问题的近似算法,并对算法的最坏性能比和渐进性能比进行理论分析。对于强NP-难问题的特殊情况,设计有效的最优算法。论文主要内容概括如下:1)生产批调度理论研究(1)两阶段流水车间生产批调度问题从炼钢与连铸生产过程中提炼出一类带有能力约束批处理机的两阶段流水车间生产批调度问题。该问题的主要特征包括:第一阶段的机器为并行批处理机,第二阶段的机器为串行批处理机,同时要求第二阶段的串行批包含第一阶段的并行批,目标函数是最小化最大完工时间。对于该问题,从理论上分析了最优解性质,基于三划分问题归结的方法证明了该问题属于强NP难问题。利用最优解性质,构造了基于动态规划的启发式算法,并从理论上分析了算法的近似性能,得到其最坏情况比为2。对于该问题的特殊情况,提出了多项式时间最优算法。通过数值计算实验,验证了启发式算法的性能。(2)带工件恶化的单机调度博弈问题从加热炉生产过程中提炼出带有工件恶化的单机博弈调度问题。在该问题中,工件的加工时间是其开始加工时间的增函数,每个工件的费用为其完工时间的函数。给定工件的初始加工次序,在构成的合作博弈调度中,工件之间的次序允许交换,从而达到节约成本的目的。针对该问题,证明了该合作博弈是凸的。提出了分配规则,并证明了该分配规则在合作博弈的核中。2)物流批调度理论研究从钢铁企业成品库的钢卷装载作业中提炼出带有车头车尾可分的装载与运输协调批调度问题。在库区中,有若干工件通过吊机装载到带有容量限制的车尾上,完成装载的车尾由可分离的车头运输到码头装船外运。该问题是决策吊机、车头和车尾如何进行匹配以完成全部工件的运输任务,使得总的运输完成时间最短。对于该问题,建立了混合整数线性规划模型,证明了该问题是强NP-难的。基于分析的最优解性质,对混合整数线性规划模型进行降维。对于中小规模问题,设计了两个分支定界算法用于求解该问题的最优解;对于大规模问题,构造了启发式算法和恢复限支搜索算法来寻找该问题的近似解,并分别对两个算法的近似性能进行了理论分析,得到了相应的最坏情况比。最后,通过科学的计算实验,验证了提出的最优算法的有效性和近似算法的性能。3)生产与物流协调批调度理论研究(1)带有两阶段运输特征的生产与物流协调批调度从冷轧生产与物流运输作业中提炼出带两阶段运输的生产与物流协调批调度问题。问题的主要特征是工件在多台并行机上进行加工,考虑加工完成的工件运到配送中心的车辆具有容量限制,经过集配后再运到不同的客户手中。对于该问题,分别以最大运输完成时间和总运输费用之和、总运输完成时间和总运输费用之和、总拖期和总运输费用之和最小化作为目标函数,研究了三种不同的情况。对于仅存在单台机器的情况,针对三类目标函数,分别构造了动态规划算法进行最优求解;对于多台机器的情况,针对三类目标函数,分别证明了计算复杂性,构造了相应的启发式算法,并对算法的最坏情况比及渐进情况比进行了理论分析。通过科学的计算实验,验证了提出的全部启发式算法的性能。(2)带有库存特征的生产与物流协调批调度从冷轧生产与物流作业中提炼出生产、库存与运输协调批调度问题。给定多个订单,每个订单包括多个工件,工件在单台机器上进行生产,再由车辆运到客户。每个订单运达客户有时间窗口限制,如果工件没有及时运出,需要存放在工序间库区中从而引起库存费用,目标是使总库存费用及运输费用最小化。对于客户订单运输可分为允许拆分和不允许拆分两种情况,分别证明了计算复杂性。对于可解情况,构造多项式时间最优算法;对于NP难情况,分别发现并证明了多项式时间内不存在具有常数最坏情况比的启发式算法,提出了基于列生成的下界和启发式算法。最后,通过科学的计算实验验证了上述提出的全部算法的性能。