The Benefit of Adaptivity in Stochastic Optimization [1/6]

Опубликовано 6 сентября 2016, 5:16

Consider the Stochastic Knapsack problem where items have deterministic values but random sizes. The motivation for this problem is in the area of stochastic scheduling where a sequence of jobs should be scheduled on a machine within a limited amount of time. The running times of jobs are considered random and independent. A priori, only some information on their probability distributions is available. When a job has been scheduled and completed, its precise running time is revealed and this information can be used in subsequent decisions. An adaptive