### 1. Introduction

In the Scheduling on Unrelated Parallel Machines problem, the goal is to find an jobs/machines assignment to minimize the overall makespan. In other words, the goal is to have the best balance between machines.

A not well balanced schedule :

### 2. Problem data

In our problem, we’ll consider * n* jobs to be assigned on

*machines.*

**m**#### 2.1 Processing time

The jobs processing time will be manage as follow :

#### 2.2 Job assignment

The jobs/machines assignment will be manage as follow : If the job ** j** is schedule on machine

**then**

*i***Xij = 1**, else

**Xij = 0**.

### 3. Genetic algorithms

#### 3.1 Introduction

In a genetic algorithm, a population of chromosomes is evolved toward better solutions. Each chromosome is defined by its genes. For each chromosome, you should be able to calculate it’s score, also called fitness.

To find better solutions, the process is:

1- **Evaluation**: Sort the population based on chromosomes scores (fitness).

2- **Selection**: Choose the best chromosomes to generate the next population (natural selection).

3- **Crossover**: Mate the chromosomes between them by mixing their genome.

4- **Mutation**: As in a natural environment, some genes are changed arbitrarily.

#### 3.2 Example

The goal is to give a practical idea of the genetic algorithm operations.

We’ll consider a problem with 2 machines (m=2) and 4 jobs (n=4).

**Population :**

Let’s generate 4 chromosomes randomly :

**Evaluation :**

Evaluation of the generated chromosomes :

**Selection :**

Select only the bests chromosomes, here we’ll choose to keep 75% of the sorted population :

**Crossover :**

1 – Choose two random chromosomes in the selected ones (the best ones).

2 – Merge these two chromosomes by mixing their genome.

3 – Store the new generated chromosome in the new population.

4 – Repeat the crossover operation until the new population is fully generated.

**Mutation:**

The mutation operation is not systematic. Usually, around 1% of the crossover chromosomes will go through a mutation.

During this operation, a random gene is arbitrarily changed:

### 4 Code example

__author__ = 'rfontenay' __description__ = 'Genetic algorithm to solve a scheduling problem of N jobs on M parallel machines' import random import time # ******************* Parameters ******************* # # Jobs processing times jobsProcessingTime = [543, 545, 854, 766, 599, 657, 556, 568, 242, 371, 5, 569, 9, 614, 464, 557, 460, 970, 772, 886, 69, 423, 181, 98, 25, 642, 222, 842, 328, 799, 651, 197, 213, 666, 112, 136, 150, 810, 37, 620, 139, 721, 823, 351, 953, 765, 204, 800, 840, 132, 764, 336, 587, 514, 948, 134, 203, 766, 954, 537, 933, 458, 936, 835, 335, 690, 307, 102, 639, 635, 923, 699, 71, 913, 465, 664, 49, 198, 747, 931, 124, 41, 214, 246, 954, 676, 811, 295, 977, 100, 316, 453, 903, 50, 120, 320, 517, 441, 874, 842] # Number of jobs n = len(jobsProcessingTime) # Number of machines m = 2 # Genetic Algorithm : Population size GA_POPSIZE = 256 # Genetic Algorithm : Elite rate GA_ELITRATE = 0.1 # Genetic Algorithm : Mutation rate GA_MUTATIONRATE = 0.25 # Genetic Algorithm : Iterations number GA_ITERATIONS = 1000 # ******************* Functions ******************* # def random_chromosome(): """ Description :Generate a chromosome with a random genome (for each job, assign a random machine). Input : -Line 2 of comment... Output : Random chromosome. """ # Jobs assignment : Boolean matrix with 1 line by job, 1 column by machine new_chromosome = [[0 for i in range(m)] for j in range(n)] # For each job, assign a random machine for i in range(n): new_chromosome[i][random.randint(0, m - 1)] = 1 return new_chromosome def fitness(chromosome): """ Description : Calculate the score of the specified chromosome. The score is the longest processing time among all the machines processing times. Input : A chromosome. Output : The score/fitness. """ max_processing_time = -1 for i in range(m): machine_processing_time = 0 for j in range(n): machine_processing_time += chromosome[j][i] * jobsProcessingTime[j] # Save the maximum processing time found if machine_processing_time > max_processing_time: max_processing_time = machine_processing_time return max_processing_time def crossover(chromosome1, chromosome2): """ Description : Crossover two chromosomes by alternative genes picking. Input : Two chromosome. Output : One chromosome. """ new_chromosome = [[0 for i in range(m)] for j in range(n)] for i in range(n): # Alternate the pickup between the two selected solutions if not i % 2: new_chromosome[i] = chromosome1[i] else: new_chromosome[i] = chromosome2[i] return new_chromosome def evolve(population): """ Description : Create a new population based on the previous population. The new population is generated by mixing the best chromosomes of the previous population. Input : Old population. Output : New population. """ new_population = [[] for i in range(GA_POPSIZE)] # First : Keep elites untouched elites_size = int(GA_POPSIZE * GA_ELITRATE) for i in xrange(elites_size): # Elitism new_population[i] = population[i] # Then generate the new population for i in range(elites_size, GA_POPSIZE): # Generate new chromosome by crossing over two from the previous population new_population[i] = crossover(population[random.randint(0, GA_POPSIZE / 2)], population[random.randint(0, GA_POPSIZE / 2)]) # Mutate if random.random() < GA_MUTATIONRATE: random_job = random.randint(0, n - 1) # Reset assignment new_population[i][random_job] = [0 for j in range(m)] # Random re-assignment new_population[i][random_job][random.randint(0, m - 1)] = 1 return new_population # ******************* Program ******************* # # Measure execution time start = time.time() # Generate an initial random population population = [[] for i in range(GA_POPSIZE)] for i in range(GA_POPSIZE): population[i] = random_chromosome() # Sort the population based on the fitness of chromosomes population = sorted(population, key=lambda c: fitness(c)) # Print initial best makespan print "Starting makespan = %03d" % (fitness(population[0])) #Iterate for i in range(GA_ITERATIONS): # Sort the population : order by chromosone's scores. population = sorted(population, key=lambda c: fitness(c)) #Generate the following generation (new population) population = evolve(population) # Print the best fitness and the execution time after iterations print "Ending makespan = %03d" % (fitness(population[0])) print "Execution time = %02d s" % (time.time() - start)

Hey Ronan,

Great article. I found your your blog, and this is a great example of your content, practical and accessible.

Good to see you are still fooling around with programming apart from within your job!

I’ll probably be in Singapore next year, but I saw you are back to Nantes… We are bound to bump into each other at some point in the future though!

See you soon

Hey Ronan,

Great job on this article. Finding a clear code about something in this field was pretty difficult. You really helped me out, I was struggling on defining the chromosomes. With the help of this code, I am able to solve a multivariate bin packing problem in a couple of minutes.

Thx!

Nice Article.

But there is one mistake. Unrelated PMS means each machine has own processing time for each job. You describe Identical PMS when each machine has same processing time for each job.

I agree, this example was as simple as possible to be easy to understand. For the final use, each job/machine has a specific time, and each job change / machine has a specific setup time as well.

code in python 3

__author__ = ‘rfontenay’

__description__ = ‘Genetic algorithm to solve a scheduling problem of N jobs on M parallel machines’

import random

import time

# ******************* Parameters ******************* #

# Jobs processing times

jobsProcessingTime = [543, 545, 854, 766, 599, 657, 556, 568, 242, 371, 5, 569, 9, 614, 464, 557, 460, 970, 772, 886,

69, 423, 181, 98, 25, 642, 222, 842, 328, 799, 651, 197, 213, 666, 112, 136, 150, 810, 37, 620,

139, 721, 823, 351, 953, 765, 204, 800, 840, 132, 764, 336, 587, 514, 948, 134, 203, 766, 954,

537, 933, 458, 936, 835, 335, 690, 307, 102, 639, 635, 923, 699, 71, 913, 465, 664, 49, 198, 747,

931, 124, 41, 214, 246, 954, 676, 811, 295, 977, 100, 316, 453, 903, 50, 120, 320, 517, 441, 874,

842]

# Number of jobs

n = len(jobsProcessingTime)

# Number of machines

m = 2

# Genetic Algorithm : Population size

GA_POPSIZE = 256

# Genetic Algorithm : Elite rate

GA_ELITRATE = 0.1

# Genetic Algorithm : Mutation rate

GA_MUTATIONRATE = 0.25

# Genetic Algorithm : Iterations number

GA_ITERATIONS = 1000

# ******************* Functions ******************* #

def random_chromosome():

“””

Description :Generate a chromosome with a random genome (for each job, assign a random machine).

Input : -Line 2 of comment…

Output : Random chromosome.

“””

# Jobs assignment : Boolean matrix with 1 line by job, 1 column by machine

new_chromosome = [[0 for i in range(m)] for j in range(n)]

# For each job, assign a random machine

for i in range(n):

new_chromosome[i][random.randint(0, m – 1)] = 1

return new_chromosome

def fitness(chromosome):

“””

Description : Calculate the score of the specified chromosome.

The score is the longest processing time among all the machines processing times.

Input : A chromosome.

Output : The score/fitness.

“””

max_processing_time = -1

for i in range(m):

machine_processing_time = 0

for j in range(n):

machine_processing_time += chromosome[j][i] * jobsProcessingTime[j]

# Save the maximum processing time found

if machine_processing_time > max_processing_time:

max_processing_time = machine_processing_time

return max_processing_time

def crossover(chromosome1, chromosome2):

“””

Description : Crossover two chromosomes by alternative genes picking.

Input : Two chromosome.

Output : One chromosome.

“””

new_chromosome = [[0 for i in range(m)] for j in range(n)]

for i in range(n):

# Alternate the pickup between the two selected solutions

if not i % 2:

new_chromosome[i] = chromosome1[i]

else:

new_chromosome[i] = chromosome2[i]

return new_chromosome

def evolve(population):

“””

Description : Create a new population based on the previous population.

The new population is generated by mixing the best chromosomes of the previous population.

Input : Old population.

Output : New population.

“””

new_population = [[] for i in range(GA_POPSIZE)]

# First : Keep elites untouched

elites_size = int(GA_POPSIZE * GA_ELITRATE)

for i in range((elites_size) ): # Elitism

new_population[i] = population[i]

# Then generate the new population

for i in range(elites_size, GA_POPSIZE):

# Generate new chromosome by crossing over two from the previous population

new_population[i] = crossover(population[random.randint(0, GA_POPSIZE / 2)],

population[random.randint(0, GA_POPSIZE / 2)])

# Mutate

if random.random() < GA_MUTATIONRATE:

random_job = random.randint(0, n – 1)

# Reset assignment

new_population[i][random_job] = [0 for j in range(m)]

# Random re-assignment

new_population[i][random_job][random.randint(0, m – 1)] = 1

return new_population

# ******************* Program ******************* #

# Measure execution time

start = time.time()

# Generate an initial random population

population = [[] for i in range(GA_POPSIZE)]

for i in range(GA_POPSIZE):

population[i] = random_chromosome()

# Sort the population based on the fitness of chromosomes

population = sorted(population, key=lambda c: fitness(c))

# Print initial best makespan

print ( "Starting makespan = %03d" % (fitness(population[0])) )

#Iterate

for i in range(GA_ITERATIONS):

# Sort the population : order by chromosone's scores.

population = sorted(population, key=lambda c: fitness(c))

#Generate the following generation (new population)

population = evolve(population)

# Print the best fitness and the execution time after iterations

print ("Ending makespan = %03d" % (fitness(population[0])) )

print ("Execution time = %02d s" % (time.time() – start))

I tried this code using DEV C++ but it doesn’t work !which programming language is it?

when I tried this code in Python it gives me a syntax error in this line,

print “Starting makespan = %03d” % (fitness(population[0]))

I don’t know where is the problem?!

Excellent boulot, ravi d’être tombé sur ton blog et de voir qu’il y a d’autres automaticiens qui font aussi de l’informatique industrielle et de la bonne façon : c’est rare.

Tes articles Python sont instructifs pour se donner de nouvelles idées au quotidien, merci.

Merci Hervé !