0
$\begingroup$

I am trying to find in the literature how to solve the following problem:

Suppose we have a list of $n$ jobs. Some of the jobs should be scheduled after other jobs (i.e., job a should be done after job b), other jobs need to be mutually exclusive (i.e., job c cannot be done concurrently with job e). Each job $i$ has a constant execution time, $T_i$. Our goal to find a scheduling for the jobs, that minimazes the time to execute all jobs.

I know that when all jobs scheduled after other jobs, this problem can be using topology ordering and dynamic programming. Also, I found this problem is highly related to makespane problem with infinite identical stations, with a contrain on the order of jobs. I did not found yet a problem given a ording/mutual exelcusive relationship between jobs.

How can we solve this problem?

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you have multiple identical machines or different speeds? $\endgroup$
    – ttnick
    Commented Jun 5, 2020 at 13:52
  • $\begingroup$ Infinite identical machines (I have edited the question) $\endgroup$
    – user3563894
    Commented Jun 5, 2020 at 13:54

1 Answer 1

Reset to default
0
$\begingroup$

OK, I found that the problem is NP-hard. Given that all jobs have only mutually exclusive relationship, and $T_i=1$ for every job $i$, the problem is eqivalent to the finding the orientation of a graph $G$, that has the minimal longest path. According to Gallai–Hasse–Roy–Vitaver theorem, this is equivalent to finding a chromatic number of $G$, which is NP-hard.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.