  The scheduling problem is a key class of optimization problems and has
various kinds of applications both in practical and theoretical scenarios. In
the scheduling problem, probabilistic analysis is a basic tool for
investigating performance of scheduling algorithms, and therefore has been
carried out by plenty amount of prior works. However, probabilistic analysis
has several potential problems. For example, current research interest in the
scheduling problem is limited to i.i.d. scenarios, due to its simplicity for
analysis. This paper provides a new framework for probabilistic analysis in the
scheduling problem and aims to deal with such problems. As a consequence, we
obtain several theorems including a theoretical limit of the scheduling problem
which can be applied to \emph{general, non-i.i.d. probability distributions}.
Several information theoretic techniques, such as \emph{information-spectrum
method}, turned out to be useful to prove our results. Since the scheduling
problem has relations to many other research fields, our framework hopefully
yields other interesting applications in the future.
