分布式估计算法优化差异工件并行批处理调度

"这篇论文探讨了在考虑差异工件的并行批处理机调度中分布式估计算法的应用，目标是优化最小化制造跨度。研究中，所有工件需按照机器容量限制分配到不同批次，然后在机器上进行处理。文章首先建立了一个混合整数规划模型，并提出了一个下界。接着，利用FF-LPT规则进行工件分批和排序。随后，作者提出了一种基于4种更新机制的分布式估计算法（EDA），用于解决该问题。通过实验仿真和与模拟退火算法（SA）、遗传算法（GA）的对比，证明了所提算法的效率和可行性。" 在并行批处理机调度中，面对差异工件的挑战，传统的调度策略可能无法有效地平衡资源利用率和制造周期。分布式估计算法（EDA）作为一种优化工具，能够有效地处理这种复杂性和不确定性。EDA的基本思想是通过构建概率模型来表示解的分布，然后通过采样和迭代更新来探索解决方案空间，从而找到接近最优解的策略。 在这篇论文中，混合整数规划模型是问题的基础，它能综合考虑离散和连续的决策变量，适应于处理包含差异工件的批次划分和机器调度问题。下界则是为了确保提出的解至少优于某个已知的最坏情况，为算法提供了一个性能基准。 FF-LPT（First Fit Decreasing Length Processing Time）规则是一种常用的工件分批和排序方法，它首先按工件的处理时间降序排列，然后尽可能地将工件放入容量允许的批次中，以最小化制造跨度。这种方法简单且有效，但可能会导致批次之间的不平衡。 EDA算法的核心在于其更新机制，通常包括基于统计学的邻域搜索、解的重采样以及遗传操作等。这些机制使得算法能够在大量随机样本中学习和改进，以适应不断变化的工件和机器条件。在论文中，作者设计了4种不同的更新策略，以期望在寻找最佳调度方案时能更好地探索和利用解决方案空间。 通过实验仿真，EDA算法的表现与模拟退火算法（SA）和遗传算法（GA）进行了比较。这三种算法都是常用的全局优化工具，各有优缺点。EDA的优势在于其能够处理复杂的依赖关系和非线性问题，而SA和GA则在跳出局部最优方面具有一定的能力。实验结果验证了EDA在解决这类问题时的高效性和适应性。 这篇论文展示了分布式估计算法在处理差异工件的并行批处理机调度问题中的潜力，为实际生产环境中的调度优化提供了新的思路和技术支持。