制造和物流系统中的物流时间与空间调度问题可以归结为整数规划问题。Branch-and-Cut算法是目前最优求解整数规划问题的有效算法之一,其基本思想为利用分支定界算法的框架结构,在其构建的分支定界树中的叶子节点处增加有效不等式用以动态提升下界(最小化问题),达到减少分支定界树分支个数,提高算法求解效率的目的。由于整数规划问题大多属于NP-难题,因此,研究Branch-and-Cut算法的改进对整数规划的最优求解的规模和效率的提升具有重要意义。本文首先以物流系统时间调度中的典型吊机调度问题为背景,对Branch-and-Cut算法进行了方法研究,以工厂吊机调度为背景进行了方法的应用研究。然后,以图论中的经典图着色问题为背景,对Branch-and-Cut算法进行了方法研究,并以物流系统的空间调度中的板坯入库垛位决策问题为背景进行了应用研究。论文主要工作及研究成果概述如下：1)典型吊机调度问题：对于由M个吊机完成N(M<N)个去向已知的待运任务,需要确定任务在吊机上的分配以及在所分配吊机上的执行顺序,在保证吊机任务之间的优先关系要求以及避免吊机间发生交叉和碰撞的同时,使得完成全部任务所需的时间最短。对该问题的整数线性规划模型采用Branch-and-Cut算法求解。基于问题特点的分析提出了有效不等式,并设计了改进的基于禁忌搜索方法的分离策略用于有效不等式的发现。数值实验的结果表明了所提算法的有效性。2)板坯库吊机调度问题：对于由M个吊机完成N(M<N)个工件的出库操作,将每个工件的连续(不中断)出库操作定义为一个任务,需要决策出库操作是否中断及全部任务在吊机上的分配及执行顺序,在满足完工顺序、避免吊机间交叉和碰撞、任务在缓冲垛位的服务规则等要求的情况下,使得所有任务的完成时间短。针对该问题建立了初始的整数规划模型,基于对问题性质分析对模型进行重建。基于具有紧下界的重建模型,设计了Branch-and-Cut算法求解。在算法实施中,提出了多类有效不等式用于提升问题下界,同时,引进变量降低技术以有效降低搜索域,进而提高算法的搜索效率。基于工业实际数据的数值实验证明了所提出算法能够在合理的时间内获得工业问题规模的最优解,其性能明显优于商业优化求解软件CPLEX,验证了提出的模型和算法的有效性。3)典型图论优化问题——图着色问题：对给定的图内的每一个顶点着一种颜色,在保证任意相连的两点着不同颜色的要求下,决策所需要的最少颜色个数。针对该问题建立了整数线性规划模型,设计了Branch-and-Cut算法进行最优求解。针对此问题,提出了变量固定策略用于削减可行域,构造了基于动态规划的有效不等式,嵌入了基于独立集的有效不等式、基于团的有效不等式,有效地提高了Branch-and-Cut算法收敛速度。通过Benchmark标准测试数据的实验结果表明了提出的算法的有效性。4)基于图着色的板坯入库垛位决策问题：对于板坯库入库的板坯,需要决策存放的垛位位置,在保证板坯按照出库顺序提取时不产生倒垛操作的要求下,使得占用的垛位数最少。该问题通过归结为图着色问题进行建模,将入库板坯定义为顶点,板坯入出库顺序定义为边,同一垛位的板坯集合定义为图中着同样颜色的点的集合,最少占用垛位数对应于最少使用的颜色数。通过图着色问题建立的板坯入库垛位决策问题模型,可以直接应用提出的Branch-and-Cut算法进行求解。数值实验验证了该问题基于图着色建模方法的有效性。5)以国内某大型钢铁企业的板坯库物流作业为背景,以上述板坯库吊机调度问题和板坯入库垛位决策问题模型和算法为内核,开发了板坯库物流优化决策支持系统。通过实际数据的应用验证,数值结果表明了所开发的模型及算法的性能优于流行的商业软件和手工编制作业方法。