## On Machine Scheduling with Exponentially Distributed Processing Times

##### Summary

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.