Solving Scheduling Problems by Simulated Annealing
Author:
- Olivier CatoniOCOlivier Catoni
- 1 September 1998
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Control and Optimization
- Vol. 36 (5) , 1539-1575
Abstract
We define a general methodology to deal with a large family of scheduling problems. We consider the case where some of the constraints are expressed through the minimization of a loss function. We study in detail a benchmark example consisting of some jigsaw puzzle problem with additional constraints. We discuss some algorithmic issues typical of scheduling problems, such as the apparition of small unused gaps or the representation of proportionality constraints. We also carry on an experimental comparison between the Metropolis algorithm, simulated annealing, and the iterated energy transformation method to see whether asymptotical theoretical results are a good guide towards practically efficient algorithms.Keywords
This publication has 14 references indexed in Scilit:
- Piecewise constant triangular cooling schedules for generalized simulated annealing algorithmsThe Annals of Applied Probability, 1998
- Sur les temps d'occupations des processus de markov finis inhomogènes à basse températureStochastics and Stochastic Reports, 1998
- The energy transformation method for the Metropolis algorithm compared with Simulated AnnealingProbability Theory and Related Fields, 1998
- The exit path of a Markov chain with rare transitionsESAIM: Probability and Statistics, 1997
- Sur les problèmes de sortie discrets inhomogènesThe Annals of Applied Probability, 1996
- Cycle Decompositions and Simulated AnnealingSIAM Journal on Control and Optimization, 1996
- $L^2$ Convergence of Time Nonhomogeneous Markov Processes: I. Spectral EstimatesThe Annals of Applied Probability, 1994
- Rough Large Deviation Estimates for Simulated Annealing: Application to Exponential SchedulesThe Annals of Probability, 1992
- Simulated annealing via Sobolev inequalitiesCommunications in Mathematical Physics, 1988
- Random Perturbations of Dynamical Systems1984