Context
In my recent research, I encounter a task assignment problem. Assuming we have a workflow, which is composed of tasks with dependencies. The workflow is a DAG (Directed acyclic graph). For each task, we have multiple systems to solve it, each with a different cost. However, if adjacent tasks are assigned to two different systems we may incur a cross-system penalty, which may increase the end-to-end cost. So the goal is to find an optimal policy to dispatch these tasks and minimize the end-to-end cost.
Formulation
Given a graph $G=\{V,E\}$ and a color set $C=\{c_0,c_1,..c_n\}$. The problem is to color the graph. The cost of a vertex depends on its color, and the cost of an edge depends on the color of its two endpoints. To be more specific, given the vertex cost function $C \rightarrow R:h(c_i)$ and the edge cost function $C \times C \rightarrow R:g(c_i,c_j)$. (specifically, $g(c,c)=0$). This problem aims to find a color mapping $V \rightarrow C:f$ to:
$min_{Args: f} Z = \Sigma_{v \in V}h(f(v)) + \Sigma_{(v,u) \in E}g(f(v),f(u))$.
(Minimize the sum of all colored vertices and edges)
Any help would be highly appreciated.