钢铁工业是国民经济的重要支柱产业之一。近年来,随着建筑业、汽车制造业、造船业和家电业的大力发展,对钢材的需求数量和质量提出了更高的要求。钢铁企业的生产过程复杂、工序之间联系紧凑、物流成网状交叉,同时由于高温连续运作特征,使得运件在各工序之间的送达时间都有严格的要求。物件在工序之间的传输主要是由运载工具——吊机完成的。有效的吊机调度能够精确物件在工序间的时间衔接、减少待料时间、提高吊机和生产设备利用率、减少资源和能源消耗。因此对钢铁工业作业管理中提炼的吊机物流调度问题进行理论分析,揭示工序及生产物流环节调度之间的内在规律,设计有效的近似算法成为运作管理领域挑战性的前沿研究课题。本文针对从冷轧罩式退火过程及钢卷仓库中提炼出的吊机调度问题,进行了理论研究。分别对罩式退火过程中工具搬运的单吊机调度问题、工具无延迟约束的多吊机调度问题、工件与工具混合搬运的多吊机调度问题、带有单服务器的并行机调度问题、吊机联运调度问题、钢卷仓库中板卷倒垛与搬运集成作业的单吊机和多吊机调度问题进行了研究。对上述问题,分别从复杂性、可解和难解方面进行了理论研究。在对问题的复杂性分析的基础上,对于可解问题,给出了多项式时间最优算法；对于难解问题,设计了有效的启发式算法,并对算法的最坏性能或渐进性能进行了理论分析,对一些特殊情况,基于对最优解的结构特征和性质分析,开发了多项式的最优算法。论文的内容概括如下：1)罩式退火过程中工具搬运的单吊机调度问题罩式退火过程中,加热罩和冷却罩作为热处理工具需要在不同的阶段装载和卸载,这些搬运任务是由吊机来完成的。对于单吊机,在给定搬运任务的情况下,如何确定吊机的搬运顺序和时间调度,使得给定的目标最小,是一个实际的优化问题。针对此问题,建立混合整数规划模型,证明了强NP难性,分析了最优解的性质；设计了一个启发式算法,并对算法的绝对性能进行了理论分析；考虑了问题的一些特殊情况,分别给出了最优解性质并构造了多项式最优算法。2)罩式退火过程中工具无延迟约束的多吊机调度问题将罩式退火过程中工具搬运的单吊机情况扩展为多台吊机情况,同时考虑了工具卸载无延迟约束,需要确定多吊机的分配、吊机路线及时间调度。对于此问题目标是最小化最大完工时间的情况,证明了这个问题的复杂度是强NP-难的,给出了避免吊机碰撞和保证工具卸载无延迟的一些可行性质；基于这些性质,提出了一个启发式算法,对算法的最坏性能进行了理论分析；对问题的特殊情况给出了多项式时间可解的证明。3)罩式退火过程中工件与工具混合搬运的多吊机调度问题该问题同时考虑了工件(板卷)和工具(加热罩、冷却罩)在退火过程中的装载和卸载操作,这些操作由多个吊机负责搬运。该问题需要确定吊机的分配、吊机的路线及时间调度。对此问题,建立了问题的一个混合整数规划模型,分析了问题的性质并给出一个整合的方法降低问题的难度同时保持了这个实际问题的本质；提出一个包括分配和调度的两阶段启发式算法,算法的有效性通过绝对性能的角度给出了分析；又提出一个基于工具分配的启发式算法,并对该算法的最坏性能和渐进性能进行了分析。4)带有单服务器的并行机调度问题冷轧并行产线工件的装载和卸载是由吊机(或搬运工具)完成的,当只有一台吊机工作时,这个调度问题可以归结为带有单服务器的并行机调度问题。与通常的单服务器并行机调度不同,该问题需要同时考虑服务器搬运工件的准备时间和移出时间。利用归结的方法证明了一些相关问题的复杂性；当并行机数目是任意的一般情况,证明了一些最优解的性质；基于这些性质,当工件在指定和不指定机器加工的两种情况下分别构造了多项式时间内可解的启发式算法；对于前者,启发式的解与最优解的比值为2,且为紧界；对于后者,LPT启发式产生的紧界为3/2-1/2/m；讨论了问题的一种多项式可解情况。5)基于重入车间调度建模策略的吊机调度问题罩式退火过程中对于同一个工件由于装卸的不同作业要求,需要由一个吊机多次完成。如果把吊机看作重入机,把加热罩和冷却罩看作两类普通机器,这个调度问题可以归结为基于重入车间调度建模策略的吊机调度问题。主要考虑两类问题：第一类问题为两类普通机各一台的情况；第二类问题为两类普通机各多台的情况。对第一类问题,证明了该问题是强NP-难的,并提出了问题的一些最优性质,给出了一个启发式算法,证明了这个算法产生的最坏性能比是6/5,且为紧界；对第二类问题,分别考虑了两个多项式时间可解的情况。6)基于混合流水车间调度建模策略的吊机联运调度问题罩式退火加工前板卷被台车运到加工车间,再由吊机从台车搬运到炉台上,退火加工后板卷由吊机向台车搬运,再由台车运到仓库,在吊机台车衔接运输的过程中,将两类运输工具分别看作机器,抽象出两阶段混合流水车间作业问题。提出了一个启发式算法,证明了该算法的最坏性能比为3-2/m1(m1,是第一阶段机器的数目)。7)钢卷仓库中板卷倒垛与搬运集成作业的单吊机调度问题该问题考虑在钢卷仓库中集成调度吊机的搬运和倒垛操作,以确定给定板卷中客户需求板卷的搬运顺序以及同时决策阻碍板卷倒垛过程中的空间流向位置、吊机路线以及时间调度。对此问题,建立了一个混合整数规划模型并证明了问题的复杂性是强NP难的；提出了问题的最优解的一些性质,基于这些性质,对问题的特殊情况提出了多项式时间最优算法；对问题的一般情况,提出了动态规划可获得小规模问题的最优解,对于大规模问题,设计了启发式算法并对启发式算法的最坏性能进行了理论分析。8)钢卷仓库中板卷倒垛与搬运集成作业的多吊机调度问题将钢卷仓库中板卷倒垛与搬运集成作业的单吊机调度问题扩展为多吊机情况,研究了多吊机同时作业保证不碰撞的情况下,集成决策钢卷仓库中需求板卷的搬运顺序与阻碍板卷的倒垛位置。对此问题,建立了一个混合整数规划模型,提出了避免吊机碰撞的一些可行性质；证明了该问题是强NP-难的,给出了问题的下界,设计了启发式算法并给出了最坏性能分析；对于问题的特殊情况给出了多项式时间最优算法。