Discrete Applied Mathematics, ( ISI ), Volume (160), No (16), Year (2012-11) , Pages (2462-2473)

Title : ( Scheduling tasks with exponential duration on unrelated parallel machines )

Authors: Mostafa Nouri Baygi , Mohammad Ghodsi ,

Citation: BibTeX | EndNote

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 Σ 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 t by worker w is a random variable expressed by a negative exponential distribution with parameter λ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.

Keywords

Stochastic parallel scheduling; Multiple choice hyperbolic 0–1
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

@article{paperid:1038776,
author = {Nouri Baygi, Mostafa and Mohammad Ghodsi},
title = {Scheduling tasks with exponential duration on unrelated parallel machines},
journal = {Discrete Applied Mathematics},
year = {2012},
volume = {160},
number = {16},
month = {November},
issn = {0166-218X},
pages = {2462--2473},
numpages = {11},
keywords = {Stochastic parallel scheduling; Multiple choice hyperbolic 0–1 programming},
}

[Download]

%0 Journal Article
%T Scheduling tasks with exponential duration on unrelated parallel machines
%A Nouri Baygi, Mostafa
%A Mohammad Ghodsi
%J Discrete Applied Mathematics
%@ 0166-218X
%D 2012

[Download]