如何改进用于作业调度的 SA 算法？

Question

 objective: max sum(solution(i,9))
---------------------------------------------
 while T>Tmin
  for iteration=100
    for i=1:61
       function(generate_possible_solutions)
       random_value = generate random value
       solution(i) = generate_possible_solution(random_value, :)
       feasible = sum(solution(i, 9))
    next

    SA:
        check feasible
        if feasible > previous_feasible
           update best
        else 
           check acceptance function
        end
        if iteration == limit
           update (T)
        end

   end For

end While

代码如上

我对工作安排有疑问。我的启发式算法使用 possible_solution 矩阵将每个作业分配给一行。例如，第 6 份工作有 140 个不同的选项，第 7 份工作在 possible_solution 矩阵中有 30 个不同的选项。

在模拟退火中，在每次迭代中，我使用其中一条解线随机进入 possible_solution 矩阵。但是，与 GAMS/Cplex 求解器相比，解最多达到 50%。

我可以使用解矩阵中的随机选择来使用模拟退火吗？我错过了什么？

Answer 1

SA:

可以从任何随机开始状态开始（S）。它不应该对解决方案产生很大影响，因为在退火的初始阶段，大多数随机提议都被接受，因为我们从高温 T 开始。所以可以使用任何随机开始状态，也可以从解决方案矩阵中选择赎金。
在退火过程中，您稍微修改了电流启动 S。不要随机选择一个新状态Q，而是稍微修改S，比如S*。
根据条件，强制检查 S* 在可行区域内。要么只修改它是可行的，要么在之后修复任何违规行为。
尝试选择有意义的邻居状态 *S。模仿人类会做什么来改善现状，例如；选择一个没有很好安排的随机工作并随机重新分配资源。随机选择一个资源也可能有效。
应该开始 T 这样大多数提案 (>90%) 都会被接受。在退火期间使用调试来获得一些比例接受状态的感觉。当几乎没有新状态被接受时，类似地选择 T_stop。
接受T_start和T_stop后，开始尝试不同的提案。它们对解决方案的质量有很大影响。（冷却方案只是几何，即 T = T * alpha 和 0 < alpha < 1。

如何改进用于作业调度的 SA 算法？

How can I improve my SA algorithm that I used for job scheduling?

algorithm

simulated-annealing

operations-research