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

Key words: operations research, dynamic spatial scheduling, genetic algorithm, heuristic location strategy

摘要： 提出了一种基于混合遗传算法的动态空间调度方法。首先利用遗传算法产生多个可行的分段调度序列,再采用动态决定分段位置的启发式算法——平均最大空闲矩形策略对遗传算法产生的调度序列进行解码。同时以完工时间和平台利用率的加权和作为适应度函数,充分考虑了空间调度问题所特有的动态性和时空关联性。遗传进化过程收敛后得到近似最优解,实现了调度方案的全局优化。对船厂实际生产数据进行了实证分析以及与其它算法的对比分析,证明了所提方法在空间调度问题上的有效性和实用性。

关键词: 运筹学, 动态空间调度, 遗传算法, 启发式定位策略