This paper provides a brief presentation of simulated annealing techniques and their application in lot sizing problems. By using a binary matrix to describe lot sizing decisions, it is ready to model this type of production/inventory system as a combinatorial optimisation problem and solve it within the simulated annealing framework. Experiments are conducted in order to understand how different aspects of the algorithm, especially the annealing schedule, affect the quality of the solution.
Simulated annealing was formally introduced in 1983 (Kirkpatrick et al., 1983), for solving combinatorial optimisation problems. It is motivated by an analogy to the thermodynamics of annealing in solids, such as growing silicon in the form of highly ordered, defect-free crystals. In order to accomplish this, the material is annealed. It is first heated to a temperature that permits many molecules to move freely with respect to each other, then it is cooled carefully, slowly, until the material freezes into a crystal, which is completely ordered, and thus the system is at the state of minimum energy. In combinatorial optimisation, simulated annealing techniques use an analogous cooling operation for transforming a poor, unordered solution into an ordered, desirable solution, so as to optimise the objective function.
One essential factor of the annealing process is the cooling schedule. Only a slow cooling ensures that a low energy state will be achieved. In gradient-based minimisation algorithms such as the Newton–Raphson algorithm, we allow only downhill moves and we always move downhill as fast as possible. However, the annealing algorithm takes not only downhill moves, but also permits uphill moves with an assigned probability depending on the state temperature. Due to introducing of this artificial noise, it is more likely that the solution set escapes from the traps of local optima (see Fig. 1). Thus, the simulated annealing technique is suitable for the optimisation problem where a desired global optimum is hidden among many, poor, local optima.To accomplish the above moves, the Metropolis algorithm (Metropolis et al., 1953) is frequently used. The probability of accepting uphill move follows a Boltzman distribution e−ΔE/Tc, where ΔE is the change of energy and Tc the current state temperature. Besides this probability, an annealing algorithm also includes the following four components:
Configuration: A description of possible problem solutions among which we search for an optimal one. Very often, the decision variables are multidimensional, discrete and have upper and lower bounds.
Cost function: An objective function to measure how well the system performs when a certain configuration is given.
Move set: A generator of random changes in the configuration. It is a set of allowable moves that will reach all feasible configurations.
Cooling schedule: A definition of the cooling speed to anneal the problem from a random solution to a good, frozen one. In its details, it must provide a starting temperature, together with the rules to determine when and how much the temperature should be reduced and when annealing should be terminated.
From this introduction, it is clear that the configuration and cost function are often attached with the nature (or simply a description) of the problem. However, the other two components, the move set and cooling schedule require deeper insights and some experience towards solving the actual problem. The quality of the simulated annealing algorithm largely depends on the design of the move set and cooling schedule. The results are the trade-off between the convergent speed and the quality of solution. A fast cooling schedule often ends up in a local optimum whereas a slow cooling schedule requires a tremendous computation time.
Finally, we would like to mention that simulated annealing is a heuristic for optimisation. It is often claimed to be a slow algorithm, due to its nature of iterative improvement, i.e. many configurations need to be visited at many state temperatures in order to obtain a good solution.
