Stochastic scheduling with Bernoulli-type jobs through policy stratification

This paper addresses the problem of computing a scheduling policy that minimizes the total expected completion time of a set of jobs with stochastic processing times on parallel identical machines. When all processing times follow Bernoulli-type distributions, Gupta et al. in 2023 exhibited approximation algorithms, improving upon an earlier algorithm by Eberle et al. for a special case. Both approximation guarantees depend on the number of machines. The present paper shows that, quite unexpectedly, the problem with Bernoulli-type jobs admits a PTAS whenever the number of different job-size parameters is bounded by a constant. The result is based on a series of transformations of an optimal scheduling policy to a "stratified" policy that makes scheduling decisions at specific points in time only, while losing only a negligible factor in expected cost. An optimal stratified policy is computed using dynamic programming. Two technical issues are solved, namely (i) to ensure that, with at most a slight delay, the stratified policy has an information advantage over the optimal policy, allowing it to simulate its decisions, and (ii) to ensure that the delays do not accumulate, thus solving the trade-off between the complexity of the scheduling policy and its expected cost. Our results also imply a quasi-polynomial approximation algorithm with a guarantee logarithmic in the number of jobs for the case with an arbitrary number of job sizes.