Expected Solution Quality

Abstract

This paper presents th e 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.