Production Scheduling Approaches
Read these sections, which highlight key problems in production scheduling. How can job sequencing and priority rules help to alleviate the key problems? Can you identify the different rules that affect job sequencing and priority rules in operations management?
4. Meta-heuristics for solving the JSSP
4.5. Simulated Annealing (SA)
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.
The Simulated Annealing model; 7a. the SA pseudo code; 7b. the flow chart of a general SA procedure
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:
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.