东北大学学报（自然科学版）

东北大学学报:自然科学版 ›› 2014, Vol. 35 ›› Issue (2): 190-194.DOI: 10.12068/j.issn.1005-3026.2014.02.009

• 信息与控制 • 上一篇    下一篇

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

王旭1,2，刘士新1,2，王佳3   

  1. (1.东北大学 信息科学与工程学院，辽宁 沈阳 110819； 2.东北大学 流程工业综合自动化国家重点实验室，辽宁 沈阳 110819；3.东北大学 工商管理学院，辽宁 沈阳 110819)
  • 收稿日期:2013-05-28 修回日期:2013-05-28 出版日期:2014-02-15 发布日期:2013-11-22
  • 通讯作者: 王旭
  • 作者简介:王旭(1982-)，男，辽宁沈阳人，东北大学博士研究生;刘士新(1968-)，男，辽宁调兵山人，东北大学教授，博士生导师.
  • 基金资助:
    国家自然科学基金资助项目(71171038，71021061)；中央高校基本科研业务费专项资金资助项目(N100504001).

Memetic Algorithm for Crane Scheduling Problem with Spatial and Temporal Constraints

WANG Xu1,2， LIU Shixin1,2， WANG Jia3   

  1. 1. School of Information Science & Engineering， Northeastern University， Shenyang 110819， China; 2. State Key Laboratory of Synthetical Automation for Process Industries， Northeastern University， Shenyang 110819， China; 3. School of Business Administration， Northeastern University， Shenyang 110819， China.
  • Received:2013-05-28 Revised:2013-05-28 Online:2014-02-15 Published:2013-11-22
  • Contact: WANG Xu
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

899

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

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

Abstract: 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.

Key words: multitask model, crane scheduling, spatial and temporal constraint, Memetic algorithm

中图分类号: