Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total duration of the tasks corresponding to each color does not exceed a constant $W$ and there exists, for each color, at least to successive activities where the elapsed time between them is greater than or equal a constant $R$

I don't know how to solve this problem or how to transform it to a know problem.

  • $\begingroup$ This is NP-hard by reduction from Knapsack ("each color does not exceed a constant $W$" is the key element), even ignoring the requirement for a "break" of length $R$. That means nobody knows a way to solve it efficiently, unfortunately. $\endgroup$ Commented Oct 13, 2019 at 12:18
  • $\begingroup$ In fact, the constant $W$ is fixed it is equal to 10 and the $R$ also. Do you think that the problem remains NP-hard? $\endgroup$
    – Farah Mind
    Commented Oct 13, 2019 at 22:52


Your Answer

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