Solution to Exercise 2: Assigning Tasks
Solve Exercise 2 of this chapter.
We'll cover the following
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 tasks and employees. The matrix 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 with size where if worker has the task assigned and otherwise.
For example, consider that is:
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 .
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.
Get hands-on with 1200+ tech skills courses.