Scheduling tasks with exponential duration on unrelated parallel machines

This paper introduces a stochastic scheduling problem. In this problem a directed acyclic graphs (DAG) represents the precedence relations among mm tasks that nn workers are scheduled to execute. The question is to find a schedule ΣΣ such that if tasks are assigned to workers according to ΣΣ, the expected time needed to execute all the tasks is minimized. The time needed to execute task tt by worker ww is a random variable expressed by a negative exponential distribution with parameter λwtλwt and each task can be executed by more than one worker at a time. In this paper, we will prove that the problem in its general form is NP-hard, but when the DAG width is constant, we will show that the optimum schedules can be found in polynomial time.