On Machine Scheduling with Exponentially Distributed Processing Times

Abstract

We address the problem to minimize the weighted sum of completion times in nonpreemptive parallel machine scheduling. We consider the stochastic variant of this problem in which the processing times are exponentially distributed random variables. We discuss the phenomenon of deliberate idleness. For some cases we prove that optimal policies are idle time free, but the general question remains unanswered. We extensively study the WSEPT list scheduling policy, and show that its perfomance guarantee is not better than 1.243. This constitutes the first lower bound for WSEPT in this setting. In particular, this bound is larger than the (tight) bound for WSPT for deterministic scheduling, which is ...... Furthermore, we show that for any list scheduling policy, the objective value of the deterministic counterpart is an upper bound for the objective value of the stochastic instance. This result holds for arbitrarily distributed processing times. For a WSEPT policy, we show that the expected objective value for an instance with exponentially distributed processing times is at least ..... times the the objective value of the deterministic couterpart, where m denotes the number of machines. Finally, we conclude with some consideratons about the computational complexity of finding an optimal policy, and of calculating the objective value corresponding to a given policy.