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

王旭^1,2，刘士新^1,2，王佳³

1. 东北大学信息科学与工程学院2. 东北大学流程工业综合自动化国家重点实验室3. 东北大学工商管理学院

摘 要：天车调度是一个NP难的多机多任务调度问题.针对炼钢-精炼-连铸生产过程中的天车调度问题,考虑时间和空间约束,建立了以钢水等待时间最少为目标的天车调度模型.提出了改进的Memetic算法,设计了采用任务分配规则和冲突处理规则的个体解码方式、PPX交叉算子和局域搜索算子;用该算法对模型进行求解,并与遗传算法进行比较.对某钢厂炼钢-精炼-连铸生产过程的天车调度问题的测试表明:与遗传算法相比,用该算法求解的等待时间最多减少16.67%,并具有很高的稳定性.

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