Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

I would be glad about some comments, ideas or solutions.


Motivation

share|improve this question

1 Answer 1

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.

If I define a total order on these vectors, the algorithms I want to apply have a mean to choose the minimum/maximum edge.

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}^{-})$).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.