patternModerate
Is the following problem NP-hard? (or have you seen it before?)
Viewed 0 times
problemtheyouhardfollowingbeforeseenhave
Problem
I genuinely don't know if the following problem is NP-hard. I have never seen it mentioned online, but it's hard to even search for exact problems like this. I have been trying to find an efficient algorithm for a while and intuitively it feels very NP-complete to me, but I haven't been able to prove it. A solution would be directly applicable to my work, if it could be found.
Problem: Assume you have $N$ different tasks which each have a unique integer length $l_n$. These tasks are arranged in a dependency tree so that each task can only be started after zero or more other tasks are completed. You also have $M$ different resources. Each task requires a given resource and each resource can only be used by one task at a time. What ordering of tasks allows for the fastest completion of the overall program (based on maximizing the amount of tasks that can be parallelized).
Example: In less abstract terms, imagine that each task is a step in a recipe. The resources are elements of a kitchen like an oven or mixer. If cooking one part of a meal requires a short use of the oven followed by a lot of manual work, and cooking the other part of the meal requires a long oven time, you should schedule the shorter cook first so that you can do the rest of the work for that component while the other half is in the oven.
Another example: Consider the dependency tree below. $a \rightarrow b$ indicates "$a$ depends on $b$". The length of a block indicates the time it takes to complete (1 or 3 in this case). There are two resources/channels: red and blue.
An example solution might look like this:
This shows that a greedy approach (like scheduling (1) and (2) simultaneously) is not sufficient -- you have to look ahead to minimize waiting for resources.
Problem: Assume you have $N$ different tasks which each have a unique integer length $l_n$. These tasks are arranged in a dependency tree so that each task can only be started after zero or more other tasks are completed. You also have $M$ different resources. Each task requires a given resource and each resource can only be used by one task at a time. What ordering of tasks allows for the fastest completion of the overall program (based on maximizing the amount of tasks that can be parallelized).
Example: In less abstract terms, imagine that each task is a step in a recipe. The resources are elements of a kitchen like an oven or mixer. If cooking one part of a meal requires a short use of the oven followed by a lot of manual work, and cooking the other part of the meal requires a long oven time, you should schedule the shorter cook first so that you can do the rest of the work for that component while the other half is in the oven.
Another example: Consider the dependency tree below. $a \rightarrow b$ indicates "$a$ depends on $b$". The length of a block indicates the time it takes to complete (1 or 3 in this case). There are two resources/channels: red and blue.
An example solution might look like this:
This shows that a greedy approach (like scheduling (1) and (2) simultaneously) is not sufficient -- you have to look ahead to minimize waiting for resources.
Solution
This problem (more formally its decision version) is NP-complete.
NP-hardness can be shown via a reduction from the Job-Shop Scheduling Problem (JSP) with makespan objective, which is well-known to be NP hard.
In the JSP, we have $n$ jobs $J_1, J_2, ..., J_n$. Within each job there is a set of operations $O_1, O_2, ..., O_n$ which need to be processed in a specific order. Each operation $o$ has a specific machine $m_o \in M$ that it needs to be processed on and only one operation in a job can be processed at a given time. (adapted from Wikipedia)
Now it is easy to see that JSP is just a special case of your proposed problem (one task per operation of JSP, dependencies only between successive operations in a job), which makes it at least NP-hard too.
Membership in NP can be shown by guessing an optimal schedule and verifying in polynomial time that it fulfills all constraints.
NP-hardness can be shown via a reduction from the Job-Shop Scheduling Problem (JSP) with makespan objective, which is well-known to be NP hard.
In the JSP, we have $n$ jobs $J_1, J_2, ..., J_n$. Within each job there is a set of operations $O_1, O_2, ..., O_n$ which need to be processed in a specific order. Each operation $o$ has a specific machine $m_o \in M$ that it needs to be processed on and only one operation in a job can be processed at a given time. (adapted from Wikipedia)
Now it is easy to see that JSP is just a special case of your proposed problem (one task per operation of JSP, dependencies only between successive operations in a job), which makes it at least NP-hard too.
Membership in NP can be shown by guessing an optimal schedule and verifying in polynomial time that it fulfills all constraints.
Context
StackExchange Computer Science Q#139551, answer score: 18
Revisions (0)
No revisions yet.