Scheduling tasks with exponential duration on unrelated parallel machines

作者：Nouri Mostafa^*; Ghodsi Mohammad

来源：Discrete Applied Mathematics, 2012, 160(16-17): 2462-2473.

DOI：10.1016/j.dam.2012.06.010

• Stochastic parallel scheduling
• Multiple choice hyperbolic 0-1 programming

This paper introduces a stochastic scheduling problem. In this problem a directed acyclic graphs (DAG) represents the precedence relations among m tasks that n workers are scheduled to execute. The question is to find a schedule Sigma such that if tasks are assigned to workers according to Sigma, the expected time needed to execute all the tasks is minimized. The time needed to execute task t by worker w is a random variable expressed by a negative exponential distribution with parameter lambda(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.

• 出版日期2012-11