  The Makespan Scheduling problem is an extensively studied NP-hard problem,
and its simplest version looks for an allocation approach for a set of jobs
with deterministic processing times to two identical machines such that the
makespan is minimized. However, in real life scenarios, the actual processing
time of each job may be stochastic around the expected value with a variance,
under the influence of external factors, and the actual processing times of
these jobs may be correlated with covariances. Thus within this paper, we
propose a chance-constrained version of the Makespan Scheduling problem and
investigate the theoretical performance of the classical Randomized Local
Search and (1+1) EA for it. More specifically, we first study two variants of
the Chance-constrained Makespan Scheduling problem and their computational
complexities, then separately analyze the expected runtime of the two
algorithms to obtain an optimal solution or almost optimal solution to the
instances of the two variants. In addition, we investigate the experimental
performance of the two algorithms for the two variants.
