graph - 使用模拟退火元启发式的作业车间调度

Question

我正在使用模拟退火实现一个作业车间调度程序 - 每个实例都由一个析取图表示（在此处描述）。基本上，元启发式的邻域动作是反转位于关键路径上的随机选择的析取弧。问题在于，在某些情况下，元启发式到达一个点，即图中的关键路径仅由连接弧组成，这导致无法反转弧的情况。有没有办法克服这个问题？

Answer 1

如果您在关键路径上只有连接弧，则您正在处理技术优先约束（即同一工作中的操作）。您无法做任何事情来缩短它们。我认为您可能已经找到了在这种情况下的最佳解决方案。