时空约束下连铸车间天车调度的多目标建模与求解

Multi-objective modelling and solving for crane scheduling with spatio-temporal constraints in casting workshop

针对钢厂炼钢-连铸车间天车调度的时空约束下NP难问题特点,考虑重钢包和空钢包吊运任务,以所有吊运任务等待被运输时间最短、总运输时间最短、天车之间负载时间差异最小为优化目标,按作业跨中多台天车执行吊运任务的时间空间约束、天车运行安全约束条件满足等为约束方程,建立了天车调度模型.设计了天车调度规则用于抽象表达其运行特征,即按吊运任务与天车的相对位置关系确定各天车与任务的匹配度,作为选择天车的指导;按天车状态及位置更新规则描述天车运行过程;按任务种类与预计起止时间先后确定吊运任务的优先级,作为天车运行过程中利用天车被动运输进行冲突消解的依据.设计了与模型特征相适应的改进遗传算法进行求解,采用某钢厂连铸跨的生产数据进行检验,通过与禁忌搜索法进行对比,证实了改进遗传算法的可行性和有效性,能够为生产过程中的天车调度提供指导.

For solving a NP-hard crane scheduling problem with spatio-temporal constraints in steelmaking- continuous casting process, a mathematical programming model was built to minimize the total waiting time of tasks, the total transportation time of tasks and the difference among the transportation time of cranes by considering full ladles and empty ladles as transportation tasks. The operation characters of cranes were concluded as such three rules, including the matching rule designed for choosing crane accord- ing to the relationship between the position of crane and the transportation task in the crane selection process, the updating rule designed for describing the evolution of state and position of cranes in the running process, the priority rule of transportation task according to the category and estimated trans- portation time of task designed for choosing collision avoidance crane in the collision resolution process. An improved genetic algorithm was used to solve the model. To validate this algorithm, experiments were conducted by using the production data in the casting span of a steel plant. By comparing with the results of tabu search algorithm, the feasibility and efficiency of improved genetic algorithm was verified, which provides a useful tool for crane scheduling in actual production.