Stochastic Optimization

In stochastic uncertainty, we again consider problems with uncertainty in the input. In contrast to the online setting we assume that the uncertain parts of the input follow some (known or unknown) fixed probability distribution.  Such probabilistic information models  a priori knowledge on the uncertain parts of the input that, for example, may stem from past statistical information.  As an example consider a scheduling problem where the processing times of the jobs are unknown but follow given probability distributions. The goal is to optimize the objective  in expectation.

As an example consider a scheduling problem where the task is to (non-preemtptively) schedule a set of given jobs on parallel identical machines in order to minimize the sum of completion times. In the stochastic variant, the processing times of the jobs are modelled by (independent) random variables and the goal is to minimize the expected sum of completion times. As part of the project, we considered algorithms based on index policies, which (up-front) assign astatic priority to each job and then schedule according to these priorities. That is, whenever a machine is free and can start to process a new job, the algorithm schedules the available job of highest priority. We showed that algorithms based on index policies do not admit constant or even distribution-independent approximation factors.