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$ – j_random_hacker Oct 13 '19 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 Oct 13 '19 at 22:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.