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

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

Code is above.

I have a problem with job scheduling. My heuristic algorithm uses possible_solution matrix to allocate each job to a line. For example, 6th job has 140 different options, 7th has 30 different options in the possible_solution matrix.

In simulated annealing, in each iteration, I use one of the solution line into the possible_solution matrix randomly. However, the solution reaches 50% at most when it is compared to GAMS/Cplex solver.

May I use the random selection from solution matrix to use Simulated Annealing? and what I have missed?

Answer 1

For SA:

• It is OK to start with any random starting state (S). It should not have a large effect on solution as in the initial phase of annealing most random proposals are accepted, because we start with a high temperature T. So it is OK to use any random start state, also ransom selection from solution matrix.
• During annealing, you slightly modify the current starte S. Don't randomly pick a new state Q, but slightly modify S, say S*.
• With condition, check of enforce that S* is within feasible region. Either only modify such that it is feasible, or fix any violations afterwards.
• Try pick neighbours states *S that make sense. Mimic what humans would do to improve a current situation, e.g; pick a random job that is not scheduled well and randomly re-allocate resources. Randomly pick a resource might also work.
• Should starting T such that most proposals (>90%) are accepted. Use debug during annealing to get some feeling of proportion accepted states. Similarly chose T_stop when almost no new states are accepted.
• After T_start and T_stop are acceptable, start experimenting with different proposals. They have large effect on quality of solution. (Cooling scheme just to geometric, i.e. T = T * alpha with 0 < alpha < 1.