# Scheduling problem

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?

• Do you have multiple identical machines or different speeds? Commented Jun 5, 2020 at 13:52
• Infinite identical machines (I have edited the question) Commented Jun 5, 2020 at 13:54

## 1 Answer

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.