Unrelated parallel machine scheduling problem heuristic : Genetic algorithm

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.

Unrelated-parallel-machine-scheduling-problem-1

A not well balanced schedule :
not-balanced-machines

A well balanced schedule :
balanced-machines

2. Problem data

In our problem, we’ll consider n jobs to be assigned on m machines.

2.1 Processing time

The jobs processing time will be manage as follow :
processing-times

2.2 Job assignment

The jobs/machines assignment will be manage as follow : If the job j is schedule on machine i then Xij = 1, else Xij = 0.
machines-jobs-assignement-table

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.

genetic-algorithm-structure

genetic-algorithm-process

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).

Processing times :
example-processing-times-table

Population :
Let’s generate 4 chromosomes randomly :
example-population-chromosomes

Evaluation :
Evaluation of the generated chromosomes :
example-population-chromosomes-evaluation

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

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.

example-population-chromosomes-crossover

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:
example-population-chromosomes-mutation

4 Code example

2 thoughts on “Unrelated parallel machine scheduling problem heuristic : Genetic algorithm”

  1. 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

  2. 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!

Leave a Reply

Your email address will not be published. Required fields are marked *