## Job Scheduling Problem with DEAP

**Problem Description**:

In job scheduling, we aim to assign jobs to machines or workers in such a way that the overall completion time (makespan) is minimized.

This is a common problem in manufacturing, project management, and computer systems where tasks need to be allocated efficiently to minimize delays and optimize resources.

#### Objective:

We have multiple jobs that need to be scheduled on different machines.

Each machine can only handle one job at a time, and jobs have different processing times.

The goal is to minimize the maximum time it takes to complete all jobs (i.e., the makespan).

We will solve this using the $DEAP$ (Distributed Evolutionary Algorithms in $Python$) library, leveraging a $Genetic$ $Algorithm$ ($GA$).

### Steps for Solving Using DEAP

**Define the Problem**:- We have
`N`

jobs and`M`

machines. - Each job has a specific processing time.
- We want to assign jobs to machines such that the overall makespan is minimized.

- We have
**Genetic Algorithm Setup**:**Individuals**: Each individual in the population represents a possible solution, i.e., a specific assignment of jobs to machines.**Fitness Function**: The fitness function will evaluate the makespan of the solution. We aim to minimize this value.**Mutation**: Swapping jobs between machines.**Crossover**: Combining two individuals (solutions) by taking part of one solution and merging it with another.**Selection**: Using tournament selection to choose the best solutions from the population.

### DEAP Implementation

1 | import random |

### Explanation

**Problem Setup**:- We defined
`N_JOBS`

as $10$ jobs and`M_MACHINES`

as $3$ machines.

Each job has a randomly assigned processing time. - The
`create_individual`

function generates a random assignment of jobs to machines.

- We defined
**Fitness Function**:- The fitness function (
`evaluate`

) calculates the makespan, which is the maximum time it takes any machine to complete its assigned jobs.

We aim to minimize this makespan.

- The fitness function (
**Evolutionary Process**:- We use genetic operators such as crossover and mutation to evolve better solutions over generations.
**Crossover**: This combines parts of two individuals (job assignments).**Mutation**: Randomly alters a small part of the individual (a job is moved to a different machine).**Selection**: The algorithm uses tournament selection to choose the best individuals to evolve in the next generation.

**Result**:- After running for $50$ generations, the algorithm returns the best job assignment and the minimum makespan.

### Sample Output:

1 | Best job allocation: [2, 1, 0, 0, 2, 0, 1, 2, 1, 0] |

### Interpretation of Results:

- The best solution indicates which jobs should be assigned to which machines, represented by a list (e.g.,
`[2, 1, 0, 0, 2, ...]`

). - The
**makespan**is the total time taken by the machine that finishes last, which in this example is $32$ units of time.

This approach demonstrates how we can use $DEAP$ to optimize a complex scheduling problem by evolving solutions to find the best possible job assignments.