Coloring an interval graph with weights
The sum coloring problem can be reduced to this problem by having $n$ possible colors with weights $u_{ij} = n - i$. Sum coloring is NP-hard for interval graphs.

Source: https://en.wikipedia.org/wiki/Sum_coloring