How to parallelize a Task Graph which has precedence constraints and resource constraints in order to obtain...
I have a Task Graph which is a DAG (Directed Acyclic Graph). Each node in the graph is a task and the edges in the graph are its dependencies/precedence constraints. This is shown in the image attached. Each task (i.e 1, 2, 3, 4, 5) is associated with a particular type of resource. There are 2 types of resources - A, B. The count of these resources can vary. For now, lets assume we have 1 resource of type A, and 1 resource of type B. A resource can execute only 1 task at a time and the tasks are non-preemptive. Resource A and B can be executed in parallel. The time taken to execute each task is also given in the graph. What is the best way to reorder the DAG such that the tasks can be executed in parallel (to obtain minimum makespan) without violating their precedence constraints?
Is the problem NP-complete? Are there scheduling algorithms/ heuristics algorithms available for such scenarios?
DAG with precedence and resource contraints
algorithm parallel-processing compiler-construction scheduling directed-acyclic-graphs
asked Nov 13 '18 at 16:35
ViniVini
82
add a comment |
I have a Task Graph which is a DAG (Directed Acyclic Graph). Each node in the graph is a task and the edges in the graph are its dependencies/precedence constraints. This is shown in the image attached. Each task (i.e 1, 2, 3, 4, 5) is associated with a particular type of resource. There are 2 types of resources - A, B. The count of these resources can vary. For now, lets assume we have 1 resource of type A, and 1 resource of type B. A resource can execute only 1 task at a time and the tasks are non-preemptive. Resource A and B can be executed in parallel. The time taken to execute each task is also given in the graph. What is the best way to reorder the DAG such that the tasks can be executed in parallel (to obtain minimum makespan) without violating their precedence constraints?
Is the problem NP-complete? Are there scheduling algorithms/ heuristics algorithms available for such scenarios?
DAG with precedence and resource contraints
algorithm parallel-processing compiler-construction scheduling directed-acyclic-graphs
asked Nov 13 '18 at 16:35
ViniVini
82
1
en.wikipedia.org/wiki/Job_shop_scheduling
– David Eisenstat
Nov 13 '18 at 16:54
Thanks! Now I know what keyword to search for :)
– Vini
Nov 14 '18 at 10:30
@DavidEisenstat I did look into Job shop scheduling but it is about executing each task on all resources. My aim is to reschedule the DAG of tasks based on their respective resource usage such that maximum parallelization of resources is achieved without violating the task's precedence contraints. I basically have to schedule the tasks to their respective resource required, in order to achieve maximum resource utilization and minimum makespan.
– Vini
Nov 26 '18 at 14:53
add a comment |
I have a Task Graph which is a DAG (Directed Acyclic Graph). Each node in the graph is a task and the edges in the graph are its dependencies/precedence constraints. This is shown in the image attached. Each task (i.e 1, 2, 3, 4, 5) is associated with a particular type of resource. There are 2 types of resources - A, B. The count of these resources can vary. For now, lets assume we have 1 resource of type A, and 1 resource of type B. A resource can execute only 1 task at a time and the tasks are non-preemptive. Resource A and B can be executed in parallel. The time taken to execute each task is also given in the graph. What is the best way to reorder the DAG such that the tasks can be executed in parallel (to obtain minimum makespan) without violating their precedence constraints?
Is the problem NP-complete? Are there scheduling algorithms/ heuristics algorithms available for such scenarios?
DAG with precedence and resource contraints
algorithm parallel-processing compiler-construction scheduling directed-acyclic-graphs
asked Nov 13 '18 at 16:35
ViniVini
82
I have a Task Graph which is a DAG (Directed Acyclic Graph). Each node in the graph is a task and the edges in the graph are its dependencies/precedence constraints. This is shown in the image attached. Each task (i.e 1, 2, 3, 4, 5) is associated with a particular type of resource. There are 2 types of resources - A, B. The count of these resources can vary. For now, lets assume we have 1 resource of type A, and 1 resource of type B. A resource can execute only 1 task at a time and the tasks are non-preemptive. Resource A and B can be executed in parallel. The time taken to execute each task is also given in the graph. What is the best way to reorder the DAG such that the tasks can be executed in parallel (to obtain minimum makespan) without violating their precedence constraints?
Is the problem NP-complete? Are there scheduling algorithms/ heuristics algorithms available for such scenarios?
DAG with precedence and resource contraints
algorithm parallel-processing compiler-construction scheduling directed-acyclic-graphs
algorithm parallel-processing compiler-construction scheduling directed-acyclic-graphs
asked Nov 13 '18 at 16:35
ViniVini
82
asked Nov 13 '18 at 16:35
ViniVini
82
asked Nov 13 '18 at 16:35
ViniVini
82
asked Nov 13 '18 at 16:35
ViniVini
82
asked Nov 13 '18 at 16:35
ViniVini
82
82
1
en.wikipedia.org/wiki/Job_shop_scheduling
– David Eisenstat
Nov 13 '18 at 16:54
Thanks! Now I know what keyword to search for :)
– Vini
Nov 14 '18 at 10:30
@DavidEisenstat I did look into Job shop scheduling but it is about executing each task on all resources. My aim is to reschedule the DAG of tasks based on their respective resource usage such that maximum parallelization of resources is achieved without violating the task's precedence contraints. I basically have to schedule the tasks to their respective resource required, in order to achieve maximum resource utilization and minimum makespan.
– Vini
Nov 26 '18 at 14:53
add a comment |
1
en.wikipedia.org/wiki/Job_shop_scheduling
– David Eisenstat
Nov 13 '18 at 16:54
Thanks! Now I know what keyword to search for :)
– Vini
Nov 14 '18 at 10:30
@DavidEisenstat I did look into Job shop scheduling but it is about executing each task on all resources. My aim is to reschedule the DAG of tasks based on their respective resource usage such that maximum parallelization of resources is achieved without violating the task's precedence contraints. I basically have to schedule the tasks to their respective resource required, in order to achieve maximum resource utilization and minimum makespan.
– Vini
Nov 26 '18 at 14:53
1
1
en.wikipedia.org/wiki/Job_shop_scheduling
– David Eisenstat
Nov 13 '18 at 16:54
en.wikipedia.org/wiki/Job_shop_scheduling
– David Eisenstat
Nov 13 '18 at 16:54
Thanks! Now I know what keyword to search for :)
– Vini
Nov 14 '18 at 10:30
Thanks! Now I know what keyword to search for :)
– Vini
Nov 14 '18 at 10:30
@DavidEisenstat I did look into Job shop scheduling but it is about executing each task on all resources. My aim is to reschedule the DAG of tasks based on their respective resource usage such that maximum parallelization of resources is achieved without violating the task's precedence contraints. I basically have to schedule the tasks to their respective resource required, in order to achieve maximum resource utilization and minimum makespan.
– Vini
Nov 26 '18 at 14:53
@DavidEisenstat I did look into Job shop scheduling but it is about executing each task on all resources. My aim is to reschedule the DAG of tasks based on their respective resource usage such that maximum parallelization of resources is achieved without violating the task's precedence contraints. I basically have to schedule the tasks to their respective resource required, in order to achieve maximum resource utilization and minimum makespan.
– Vini
Nov 26 '18 at 14:53
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53285558%2fhow-to-parallelize-a-task-graph-which-has-precedence-constraints-and-resource-co%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53285558%2fhow-to-parallelize-a-task-graph-which-has-precedence-constraints-and-resource-co%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
en.wikipedia.org/wiki/Job_shop_scheduling
– David Eisenstat
Nov 13 '18 at 16:54
Thanks! Now I know what keyword to search for :)
– Vini
Nov 14 '18 at 10:30
@DavidEisenstat I did look into Job shop scheduling but it is about executing each task on all resources. My aim is to reschedule the DAG of tasks based on their respective resource usage such that maximum parallelization of resources is achieved without violating the task's precedence contraints. I basically have to schedule the tasks to their respective resource required, in order to achieve maximum resource utilization and minimum makespan.
– Vini
Nov 26 '18 at 14:53