论文部分内容阅读
钢铁企业的生产过程非常复杂,钢铁工业生产兼有连续和离散生产特性,各阶段生产间联系紧密,连续生产要求在线处理具有实时特征;使用生产设备多且机器环境复杂,生产设备大而使得物料多以批成组方式进行生产;生产环节之间存在运输,运输工具种类繁多、容量各异,不同类型运输工具之间存在连接;需要加热的过程多,高温工件有潜热余热,生产运输高温运作使物流带有热链特征;生产过程产线长、工序多,生产中缓冲环节多,工艺路线复杂使得生产物流流向带有交叉网状特征,能源和资源消耗大。有效的钢铁生产与物流调度能够缩短产品生产周期、提高产品质量、减少在制品库存、减少资源和能源消耗、降低生产成本。由于钢铁企业生产过程一些新的特征和约束增加了对这个过程进行生产与物流调度的难度,因此对钢铁工业的生产与物流调度进行理论分析、揭示工序及生产物流环节调度之间的内在规律、对复杂和难求解的问题设计有效的近似算法成为生产上迫切需要解决且具有挑战性的研究课题。 本文针对从炼钢、初轧的实际生产过程中提炼出来的一类生产与物流调度方面的问题,进行了理论研究。基于算法复杂性和NP-理论,分别对不同的调度问题进行了复杂性分析。对于易解的问题,给出了多项式时间最优算法。对于难解的问题的一般情况,给出NP-难证明,构造有效的启发式算法,并通过最坏情况分析或数值计算实验来分析验证所提出的算法的有效性;对难解问题的一些特殊情况,从理论上分析了最优解的结构特征和性质,并开发了有效的算法来获得问题的最优解。整个论文的具体内容概括如下: (1)从钢铁企业钢锭的模铸和均热过程中提炼出一类带运输的两机流水车间调度问题,其中第一台机器是单机而第二台机器是批处理机。两个机器间存在一个运输车辆,该车每次能搬运多个工件,往返运输总时间为一个常数T,目标是最小化makespan。对该问题,建立了混合整数规划模型,并利用三划分问题证明它是一个强NP-难问题。提出一个启发式算法来寻找该问题的近优解,并对该算法进行了最坏情况性能分析。通过数值计算实验,表明了启发式算法求解这个调度问题的有效性。 (2)从钢铁企业钢锭的均热和轧制过程中提炼出一类第一台为批处理机而第二台为单机且机器间带运输的两机流水车间调度问题。运输车辆每次能搬运多个工件,往返运输总时间为T,目标是最小化makespan。通过三划分问题证明这个调度问题是一个强NP-难问题,并且对该问题建立了混合整数规划模型。对于小规模问题,用CPLEX来求解提出的混合整数规划模型,可以得到最优解。对于大规模问题,提出一个启发式算法来求解问题的近优解,并分析了启发式算法的最坏情况性能,同时通过数值计算实验验证提出的启发式算法的有效性。 (3)以钢铁企业钢锭的均热和轧制过程为背景,研究带恶化工件且含批处理机的两机流水车间调度的问题。首先研究第一台是单机、第二台是容量为c的批处理机并且恶化工件在单机上加工的调度问题,对目标为最小化makespan、总完工时间以及最大延迟问题,分别给出多项式时间最优算法。其次研究第一台是容量为c的批处理机、第二台是单机并且恶化工件在单机上加工的调度问题,对目标为最小化makespan,提出多项式时间最优算法;对目标为最小化总完工时间,证明它是一个强NP-难问题,并且对其一个特殊情况给出多项式时间最优算法。 (4)从钢铁企业的炼钢-连铸过程中提炼出一类带批调度和工件动态到达的两机流水车间调度问题。第一台机器一次加工一个工件,而第二台机器以批的形式加工工件。工件动态到达第一台机器,在第二台机器上只要形成一批,就会产生一个常数安装调整时间,批的加工时间定义为这一批里所有工件的加工时间之和加上安装调整时间。目标是最小化makespan。对该调度问题,建立混合整数规划模型,并得到此问题一个下界。证明这个调度问题是一个强NP-难问题,提出一些基于动态规划的启发式算法来寻找这个问题的近优解,通过数值计算实验来检验提出的启发式算法的有效性。 (5)从钢铁企业的精炼过程中提炼出一类带吊机运输不碰撞约束的并行机调度问题。工件在精炼区的精炼炉上加工完成后,它们由一些吊机运输。吊机运行在所有生产设备的上方,同一跨内的两个吊机是在同一轨道上运动,吊机之间不能交叉碰撞。目标是最小化makespan。对这个调度问题,建立混合整数规划模型,证明该调度问题是强NP-难的,得到问题的两个下界,并提出一些最优解性质。为了找到问题的有效调度,提出启发式算法,通过数值计算实验来验证提出的启发式算法的有效性。 (6)以钢铁企业精炼后的连铸和模铸调度为背景,研究一类带恶化工件的two-agent单机调度问题。两个agent在共用的单机上竞争地加工各自的工件,对工件考虑三个恶化函数。对满足B-agent的最大费用约束下最小化A-agent的总完工时间的三个问题以及对满足B-agent的makespan约束下最小化A-agent的最大延迟的三个问题,先提出问题的一些最优解性质,接着给出多项式时间最优算法来求解所考虑的问题。基于得到的结果,获得满足agent B目标函数值不超过一个给定的上界U的要求下最小化agentA目标函数的这类问题的一般性质。