Scheduling tasks with exponential duration on unrelated parallel machines |
| |
Authors: | Mostafa Nouri Mohammad Ghodsi |
| |
Institution: | 1. Computer Engineering Department, Sharif University of Technology, Tehran, Iran;2. Institute for Research in Fundamental Sciences (IPM), Tehran, Iran |
| |
Abstract: | This paper introduces a stochastic scheduling problem. In this problem a directed acyclic graphs (DAG) represents the precedence relations among tasks that 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 by worker is a random variable expressed by a negative exponential distribution with parameter 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|