求解具有时空约束的天车调度问题Memetic算法  

Memetic Algorithm for Crane Scheduling Problem with Spatial and Temporal Constraints

作　　者：王旭[1,2] 刘士新[1,2] 王佳[3] 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110819 [2]东北大学流程工业综合自动化国家重点实验室,辽宁沈阳110819 [3]东北大学工商管理学院,辽宁沈阳110819

出　　处：《东北大学学报（自然科学版）》2014年第2期190-194,共5页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金资助项目(71171038;71021061);中央高校基本科研业务费专项资金资助项目(N100504001)

摘　　要：天车调度是一个NP难的多机多任务调度问题.针对炼钢-精炼-连铸生产过程中的天车调度问题,考虑时间和空间约束,建立了以钢水等待时间最少为目标的天车调度模型.提出了改进的Memetic算法,设计了采用任务分配规则和冲突处理规则的个体解码方式、PPX交叉算子和局域搜索算子;用该算法对模型进行求解,并与遗传算法进行比较.对某钢厂炼钢-精炼-连铸生产过程的天车调度问题的测试表明:与遗传算法相比,用该算法求解的等待时间最多减少16.67%,并具有很高的稳定性.A crane scheduling problem is a multi-machine, multi-task and NP-hard problem. For the problem in the steelmaking-continuous casting production process, a model was proposed to minimize the waiting time of molten steel, with temporal and spatial constraints considered. An improved Memetic algorithm was developed to solve the model, in which individual decoding based on task allocation rules and conflicts eliminating rules, PPX crossover operator and local search（LS） operator were designed, and it was also compared with the genetic algorithm. The solution to the model with the improved algorithm for a practical problem showed that the waiting time was reduced by 16.67% at most with high stability, in comparison with the genetic algorithm.

关 键 词：多任务模型 天车调度 时空约束 MEMETIC算法 

分 类 号：C934[经济管理—管理学]