JSSP

JSSP is a Job Shop Scheduling problem solver using a Genetic Algorithm implementation. Given a finite set of jobs, each consisting of a series of operations, with each operation being performed by a given machine in a set amount of time. It must also be taken into account that each operation can have other operations as dependencies and some operations can be performed in parallel. The goal of this program is to find an optimal arrangement of operations by minimizing the makespan. The makespan can be defined as the total time to perform all of the operations.

Jobs and Operations representation

An operation is represented as an object attributes:

• Name
• Machine where that operation is supposed to be ran
• The time it takes to be carried out
• The radiator model to which it belongs
• ID of the job instance to which it belongs
• List of operations that it depends on
• Assigned starting time

Each operation belongs to a job instance, while each job has a list of operations that integrate it.

Operations can only be performed in their assigned machine, however multiple machines can be ran in parallel.

Evolutionary aspect

Each series of operations is represented by a genome, which in JSSP is a list of Operation objects, each object being an individual gene. In this genome, the order of elements indicates which operation should be performed first

###Initial Population The initial population is generated by randomly selecting the operations that have no dependencies. Then operations that have had their dependencies satisfied are selected randomly. It is considered that if an operation has already been selected, it counts as a satisfied dependency. This process is repeated for each genome until the set population size is reached.

###Mating To mate, the algorithm selects two genomes as parents randomly from the existing population. It then selects a fixed amount of genes from one parent randomly, and then selects the remaining genes from the second parent to produce the first child. The second child is then produced with the remaining unused genes from each parent. Special care is taken to ensure that the selected genes from both parents are not duplicated, and to preserve the order of each gene in the offspring relative to their original position in their parents.

###Mutation Each offspring has a set probability of mutating after it has been generated. This mutation consists in taking a fixed percentage of the trailing genes in the genome, and rearranging the genes randomly while taking care in not violating dependencies. (Using a similar algorithm to the one used in the generation of the initial population)

System requirements

• Python 3.5.x
• matplotlib

How to run it

Simply run

$ python main.py