最小时间窗规则及其在混合遗传算法中的应用

为了研究与优先规则结合的混合遗传算法,提出了最小时间窗规则(STW),设计了采用最小时间窗规则生成初始种群的算法.发现调度结果中时间窗越少和越小,则完工时间就越小.探讨了优先规则应用于遗传算法中在生成初始种群时的完工时间、广义海明距离和完工时间的标准偏差等性能指标.对不同规模基准调度问题的测试结果表明,STW规则在以最小化完工时间为目标的调度中,与其他几种简单规则相比,能产生较好的调度效果.在混合遗传算法中,采用STW规则产生的初始种群整体适应度最高,多样性较好.

Shortest Time Window Rule and Its Application in Hybrid Genetic Algorithm

To study hybrid genetic algorithm combined with priority rules,shortest time window rule(STW) is put forward,initial population generation algorithm with STW is designed.It is found that the fewer and shorter time windows in scheduling results are,the less the processing time is.Several performance indexes of priority rules used in genetic algorithm's initial population generation are discussed,such as make span,generalized Hamming distance,and make span's standard deviation.The test result to solve different scales benchmark scheduling problem shows that STW can generate better scheduling results than other simple priority rules do,and the initial population generated with STW has better fitness and diversity in hybrid genetic algorithm.