Expected solution quality
John L. Bresina, Mark Drummond, Keith J. Swanson · 1995
This paper presents the Expected Solution Quality (esq) method for statistically characterizing scheduling problems and the performance of schedulers. The esq method is demonstrated by applying it to a practical telescope scheduling problem. The method addresses the important and difficult issue of how to meaningfully evaluate the performance of a scheduler on a constrained optimization problem for which an optimal solution is not known. At the heart of esq is a Monte Carlo algorithm that estimates a problem's probability density function with respect to solution quality. This "quality density function" provides a useful characterization of a scheduling problem, and it also provides a background against which scheduler performance can be meaningfully evaluated. esq provides a unitless measure that combines both schedule quality and the amount of time to generate a schedule. 1 Introduction This paper presents a method for statistically characterizing both scheduling problems and the p...