基于改进遗传算法的单机成组作业调度

摘要

提出了单机成组作业调度的改进遗传算法.优化目标为总流程时问的单机成组作业调度问题明显是NP-hard问题,此问题的多项式求解方法不能求取最优解,而一些启发式算法也只能求出此问题的次优解.为获得单机成组作业最优调度,通过采用整数实值编码,随机采样选择,单点交叉以及变异检查,设计了单机成组作业调度的改进遗传算法.仿真结果表明,算法能够找到此问题的最优解,其性能优于加权最短加工时间(WSPT)启发式算法.改进遗传算法能够灵活解决各种单目标调度及多目标调度问题.