# Edge weight function for graph instance of scheduling and allocation problem

I have difficulties developing a proper (non-scalar) edge cost function $c_e$ for my resource scheduling problem, which I mapped into a graph problem.

Processes $P_i$ need resources $R_i \in \mathcal{R}$. Since there is a fixed amount of resources, we can depict the requirements of a given process $p$ as vector $v_p \in \mathbb{N}^{|\mathcal{R}|}$.

Each node of the graph is a process $p$ with his corresponding $v_p$.

For $\begin{array}{|c|c|c|c|} \hline & R_0 & R_1 & R_2 \\ \hline P_0 & 2 & 2 & 1\\ \hline P_1 & 3 & 3 & 2\\ \hline \end{array}$ we have $v_{p_0} = \left( \begin{array}{c} 2\\ 2\\ 1 \end{array} \right)$ and $v_{p_1} = \left( \begin{array}{c} 3\\ 3\\ 2 \end{array} \right)$

• $v_{p_1}-v_{p_0} = \left( \begin{array}{c} 1\\ 1\\ 1 \end{array} \right)$ means we can switch from $p_1$ to $p_0$ without allocating new resources, we even have excess of $3 = \| v_{p_1}-v_{p_0} \|_1$. One has $p_0 \subseteq p_1$ (You can't use the manhatten norm if the components of the difference vector are positive and negative).

• $v_{p_0}-v_{p_1} = \left( \begin{array}{c} -1\\ -1\\ -1 \end{array} \right)$ means, if we want to switch from $p_0$ to $p_1$, we have to allocate one of each resource type.

Based on this model, I would like to derive a cost function for the edges, so that I can search for an optimal hamilton circle on the resulting graph (e. g. TSP) to get a path consisting all vertices, i. e. a optimal execution sequence for the processes with minimum allocation cost.

I thought of a function $c: (P, P) \rightarrow (\mathbb{N},\mathbb{Z}^{-})$ that returns a tuple with total excess and total deficit. But a tuple as edge weight seems kind of unfamiliar to me. Currently I'm experimenting with vector metrics, e.g. dot product and trying to find a reasonable use there. But it's not that easy.

Motivation

-

After thinking about it. I'm favoring the idea of using the difference vector $d_{p_x,p_y} = v_{p_x}-v_{p_y}$ as edge weight.
Also no information is lost (It also wouldn't be lost, if I had a bijective weight function $c(e) \rightarrow \mathbb{Z}$ or $c(e) \rightarrow (\mathbb{N},~\mathbb{Z}^{-})$).