Solution to Exercise 2: Assigning Tasks

The remaining exercises are challenging to solve with PSO. When we think of solutions to these problems, it’s hard to define a velocity for them. Using a genetic algorithm is more natural—and that’s why we’ll do just that.

Exercise 2

In this problem, we have $n$ tasks and $m$ employees. The matrix $W$ tells us how much time each employee needs to do each task. What would a solution for this problem look like?

In this case, a solution is an assignment of each task to some worker. There could be workers with no tasks assigned and workers with multiple tasks assigned. Mathematically, we can think of a solution as a matrix $S$ with size $m \times n,$ where $S_{i,j} = 1$ if worker $i$ has the task $j$ assigned and $S_{i,j} = 0$ otherwise.

For example, consider that $S$ is:

$$\left(\begin{array}{cc} 1 & 0\\ 0 & 1 \end{array}\right)$$

Then we assign task 1 to worker 1 and task 2 to worker 2. The total time is the longest time that it takes for a worker to complete their tasks. We can calculate those times using matrix $W$.

We’re going to use the following operations in our genetic algorithm:

• mutation: We reassign a task to another worker.

• crossover: We combine the first columns of one solution with the last columns of the other.

• score: The score will be the inverse of the total time.

To check how good our solution is, we can use the function exact_solution that’s already defined. This function is hidden since we’ll only use it to compare our results.