BUS606: Operations and Supply Chain Management

The simulated annealing was presented by Scott Kirkpatrick et al. in 1983 and by Vlado Černý in 1985. This optimization method is based on works of Metropolis et al., which allows describing the behaviour of a system in thermodynamic equilibrium at a certain temperature. It is a generic probabilistic metaheuristic used to find a good approximation to the global optimum of a given objective function. Mostly it is used with discrete problems such as the main part of the operations management problems.

Name and inspiration come from annealing in metallurgy, a technique that, through the heating and a controlled process of cooling, can increase the dimensions of the crystals inside the fuse piece and can reduce the defects inside the crystals structure. The technique deals with the minimization of the global energy E inside the material, using a control parameter called temperature, to evaluate the probability of accepting an uphill move inside the crystals structure. The procedure starts with an initial level of temperature T and a new random solution is generated at each iteration, if this solution improves the objective function, i.e., the E of the system is lower than the previous one. Another technique to evaluate the improvement of the system is to accept the new random solution with a likelihood according to a probability exp(-ΔE), where ΔE is the variation of the objective function. Afterwards a new iteration of the procedure is implemented.

As follows there is the pseudo-code of a general simulated annealing procedure:

Figure 7. 

For the scheduling issues, the application of the SA techniques requires the solutions fitness generated by each iteration, that is generally associated to the cost of a specific scheduling solution; the cost is represented by the temperature that is reduced for each iteration. The acceptance probability can be measured as following:

$A i j=\left\{\min \left[1, \exp \left[\left(-\frac{C(j)-C(i)}{c}\right)\right]\right]\right\}$    E14

Another facet to be analysed is the stopping criteria, which can be fixed as the total number of iterations of the procedure to be computed.