模拟退火遗传算法SAGA解决差异工件批调度问题

差异工件平行机批调度问题是工业生产中常见的复杂优化问题，它涉及到如何有效地安排多台平行机器对具有不同加工时间、优先级或约束条件的工件进行排序和分配，以最小化总加工时间和资源利用率。针对这一问题，本文提出了模拟退火遗传算法（SAGA），结合了模拟退火算法（SA）的全局搜索能力和遗传算法（GA）的局部优化特性。 模拟退火遗传算法（SAGA）的核心在于将SA的状态转移操作融入到基于最优保留的GA中。状态转移操作作为局部搜索策略，有助于算法跳出局部最优解，提高搜索效率。在GA的常规迭代过程中，特别是在后期，由于适应函数可能无法准确区分适应度相近的个体，SAGA采取了两阶段标定适应函数的方法，以增强算法的全局性能。在进化后期，SAGA引入了一个加速适应函数，这有助于更快地收敛到全局最优解。 此外，文章还改进了传统的单切点交叉方式，采用了效果更好的双切点交叉，这可以提高种群的多样性，防止过早陷入局部最优，从而提升算法的整体性能。实验结果对比显示，SAGA相较于其他常见的方法，如GA、BFLP(T)（最佳适应度最短加工时间）和FFLP(T)（第一个适应度最短加工时间）启发式规则，表现出显著的优势，证明了其在解决差异工件平行机批调度问题上的有效性。 研究团队由舒锋、陈华平、杜冰、李小林和操张进组成，分别来自中国科学技术大学管理学院，他们的工作涵盖了智能优化、作业调度以及相关领域的深入研究。他们的研究成果对于优化生产流程，提高生产效率和降低成本具有重要的理论和实际意义。整个研究得到了国家自然科学基金和国家博士点基金的共同支持。该论文发表在2010年，表明了学术界对该问题的关注和持续的研究进展。