混合遗传-模拟退火算法解决有限缓冲并行机调度问题

"王炳刚、饶运清、邵新宇和王孟昌在2009年的《华中科技大学学报(自然科学版)》第37卷第5期上发表的文章，探讨了解决带有限中间缓冲区的多级并行机问题。他们提出了一种结合遗传算法和模拟退火算法的混合求解方法，以最小化最大完工时间为优化目标。" 在多级并行机问题中，通常涉及到多个加工阶段和多台机器，工件在这些机器之间传递并进行加工。由于中间缓冲区的容量有限，这个问题变得复杂且具有挑战性。有效的调度策略对于提高生产效率和减少等待时间至关重要。 该研究中，作者将搜索空间局限于第一工位工件的投产序列置换向量空间，以此为基础构建整个调度方案。他们创新性地设计了一种由第一工位工件投产序列向量来生成全局调度策略的方法。在算法设计上，他们采用了混合交叉算子和变异算子，这两种算子分别来自遗传算法和模拟退火算法，以增强算法的探索能力和局部最优解决方案的跳出能力。 混合交叉算子是遗传算法中的一个重要组成部分，它负责生成新的解决方案，通过组合两个父代个体的部分特征来创建后代。而变异算子则有助于保持种群的多样性，防止算法过早陷入局部最优。这种结合两种优化算法的策略旨在平衡全局搜索和局部搜索，以找到更优的调度方案。 通过与已有的计算结果对比，研究者证明了所提出的混合算法在解决这类问题时的可行性和优越性。这表明该算法能有效地处理有限中间缓冲区条件下的多级并行机调度问题，对于实际工业生产环境中的调度优化具有重要意义。 关键词涉及到并行机、有限中间缓冲区、调度、遗传算法和模拟退火算法，这些是该研究的核心概念。根据中图分类号，该研究属于机械制造技术和计算机科学领域的交叉应用。文献标识码A表示这是一篇原创性的科研论文。 这篇论文提供了一种创新的混合算法，解决了在有限中间缓冲区约束下多级并行机的调度问题，对于提升生产系统的效率和降低最大完工时间有显著作用。