摘要
提出了一种基于混合遗传算法的动态空间调度方法。首先利用遗传算法产生多个可行的分段调度序列,再采用动态决定分段位置的启发式算法——平均最大空闲矩形策略对遗传算法产生的调度序列进行解码。同时以完工时间和平台利用率的加权和作为适应度函数,充分考虑了空间调度问题所特有的动态性和时空关联性。遗传进化过程收敛后得到近似最优解,实现了调度方案的全局优化。对船厂实际生产数据进行了实证分析以及与其它算法的对比分析,证明了所提方法在空间调度问题上的有效性和实用性。
In this paper we propose a dynamic spatial scheduling approach based on hybrid genetic algorithm(GA).GA is used to determine the optimal processing sequence.In the process of decoding,the location of work pieces is determined by a dynamic heuristic location strategy,called an average maximized idle rectangle strategy.We use the weighted completion time and space utilization as the fitness function,which fully considers the dynamic nature and the correlation between time and space in a space schedule problem.Every individual in population is a scheduling sequence,and the optimal solution can be found in the process of evolution.Finally,the effectiveness and the practicability of the algorithm are confirmed by both a simulation study and empirical comparative study based on the actual data of a shipyard.
出处
《运筹与管理》
CSSCI
CSCD
北大核心
2013年第2期99-104,共6页
Operations Research and Management Science
基金
国家自然科学基金资助项目(70871057
71171100
70971056)
关键词
运筹学
动态空间调度
遗传算法
启发式定位策略
operations research
dynamic spatial scheduling
genetic algorithm
heuristic location strategy