Welcome to i4QLRT

Make / Assembly Line Balancing Problem / Metaheuristics / Genetic Algorithm

This is the python code of a Genetic Algorithm to solve the Assembly Line Balancing Problem.

Problem description

TThe Assembly Line Balancing Problem (ALBP) is a production planning problem that seeks to optimize the assignment of tasks to workstations on an assembly line to meet a required production rate while minimizing costs. In the ALBP, a set of tasks must be assigned to a set of workstations along a production line, with each task having a predetermined processing time and each workstation having a maximum capacity, defined by the maximum cycle time. The objective is to minimize the number of workstations required and to minimize the total idle time of the workstations.

A given number of T tasks should be executed in W workstations. Tasks can have predecessors, therefore a task can be assigned to a workstation only if all the predecessors have been assigned to previous workstations or to such workstation. The problem is to determine the optimal such arrangement, i.e. the one with the shortest possible total job execution makespan.

The number of possible solutions in the ALBP is equal to W multiplied by itself T-1 times, or W^(T-1). For example, if there are 5 workstations and 60 tasks, the total number of possible solutions in the ALBP is 5^59 = 173,472,347,597,680,709,441,192,448,139,190,673,828,125. The ALBP is a combinatorial optimization problem and can be solved using various heuristic and exact algorithms.

Algorithm description

A Genetic Algorithm (GA) is a metaheuristic inspired by the process of natural selection. In this GA for solving the Group Technology Problem, each individual is a possible sequence of jobs, the population is composed of a certain number of individuals, the evolution of the population is based on the crossing of 2 individuals (father and mother) to obtain a new individual (child) that can be mutated. There are different crossover and mutation modes that can be used depending on the characteristics of the problem to be solved. The algorithm can be structured in 6 steps:

• Step 1 The initial population is created by random sequence generation. The makespan of all individuals is calculated. A fitness is assigned to each individual as the maximum makespan of the entire population minus the makespan of the individual, so the higher the fitness the better the individual (lower makespan).
• Step 2 Two individuals are randomly drawn from the population, but giving more opportunity of choice to the individuals with better fitness, using the roulette method.
• Step 3 The two individuals (father and mother) extracted are crossed. The two parents selected for crossover are cut at two random cut-points. The offspring takes the same genes outside the cut-points at the same location as its parent and the genes in between the cut-points are scrambled according to the order that they have in the other parent. Since both parents are feasible, both children must also be feasible. In this way two new individual (children) are generated. The fitness of the new individuals is calculated.
• Step 4 Each child is always mutated. Mutation consists of making a gene swap in each of the layers. This ensures that the mutated child remains feasible. The fitness of the mutated child is calculated.
• Step 5 Both the child and the mutated child are inserted into the population, replacing the worst individuals in the population. Before insertion, they are checked to see if they already exist in the population, in which case they are not inserted.
• Step 6 Return to Step 2, repeating the loop until the stopping rule is reached (e.g. an amount of computational time or a number of loops).