2
$\begingroup$

Let me tell you the story of this problem. We have $n$ projects and $m$ workers. Each worker can work on multiple projects and each project can be solved by multiple workers. This relationship can be easily described by an $n \times m$ matrix $A$ where $a_{i,j}=1$ means that worker $j$ works on project $i$.

Matrix $A$ is typically quite sparse and we would like to see at a glance who works on what project and with whom. The best result would be to permute the rows and columns of the $A$ matrix to make it somehow diagonal. Since $n\neq m$ in general, the only criterion I imagine is the minimization of gaps from the diagonal.

General question: What approach to use to permute the rows and columns to have (i) workers working on the same projects near each other and (ii) projects being solved by same workers near each others.

My attempt:

Without loss of generality, we can focus on those permutations that have $a_{1,1}=1$. Let us define a set of matrix indices $S$ where

  • $(1,1)\in S$
  • if ${(i,j)}\in S$ and $a_{(i,j+1)}=1$, then $(i,j+1)\in S$
  • if ${(i,j)}\in S$ and $a_{(i,j+1)}=1$, then $(i,j-1)\in S$
  • if ${(i,j)}\in S$ and $a_{(i,j+1)}=1$, then $(i+1,j)\in S$
  • if ${(i,j)}\in S$ and $a_{(i,j+1)}=1$, then $(i-1,j)\in S$

In the other words, $S$ are all indices that you can "walk to" from $(1,1)$ passing the one-elements only.

For each matrix index $(i,j)$, we define the distance $d$ from $S$

  • if $(i,j)\in S$ then $d((i,j),S)=0$
  • otherwise $d((i,j),S)$ is the minimal number of gaps in matrix $A$ I have to pass to reach $S$

The optimality criterion would be to find the permutation of both rows and coluumns so the average distance from $S$ is minimal. This criterion I would minimize by means of evolutionary algorithms.

I wonder if there is not something more tailored.

$\endgroup$
1
$\begingroup$

It seems to me that you could treat this as a clustering problem, where the "linkage" between two tasks is the number of shared workers, and the "linkage" between two workers is the number of shared tasks, and the distance between two workers (or tasks) is something like $e^{-\ell}$, where $\ell$ is the linkage.

Now you can apply a spectral clustering algorithm to the worker set and to the task set, using this notion of distance. (a few lines of Matlab do this -- see the paper on "Spectral Clustering" by Andrew Ng et al. for code).

I'm not sure whether this is really what you're after, but it might be a reasonable start.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

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