Optimization of Production Lines using Simulation and Genetic Algorithms

Introduction

In this project a genetic algorithm has been implemented from scratch, for the optimization of the scheduling production line of a textile industry. Production scheduling aims to maximize the efficiency of the operation and reduce costs. Companies use scheduling to allocate all the necessary resources (plant and machinery, human resources), to plan the production processes and purchase materials. The production line of this industry is described as a Flexible Flow Shop.

Simulation of the system

The simulation of the discrete event system is implemented in C++ and imitates the jobs that each machine is performing over time. The type of this specific manufacturing system is a job shop. N jobs J1, J2, …, Jn of varying sizes are given, which have to be assigned to M machines. The output that we are most concerned in this system is the make-span, which is the total length of the schedule (when all the jobs have finished processing). Other quantities that give a representation on the efficiency of the system can also be calculated easily.

For every moment in time there is a specific event that will take place. For example the placement and the cutting of the fabric.

A Genetic Algorithm for the optimization part

A genetic algorithm was implemented from scratch. Its main purpose is to find the best possible production plan in terms of time. The job shop problems in general are NP-complete.

The main steps of this GA are the followings:

• Initialization. Many individual solutions are generated. Each solution is a specific production plan. This production plan there is an ordered list of jobs/orders.
• A fitness function that evaluates the production plan/solution.
• Selection process. A proportion of the existing population is selected to breed a new generation. The best production plans have more chances to survive.
• Genetic operators such as mutation and crossover. In addition, a new operator is defined to help the algorithm escape from the local minimal.
• Termination, the highest ranking solution has reached a plateau where no possible improvements can be found.

Fig. 4 illustrates the process of the selection. Every solution is described as an ordered list. For example the parent 1 has the following production plan: 2, 3, 5, 1, 8, 6, 9, 7, 10, 4. First goes the order 2 which has many jobs, then order 3 is prepared. Some jobs of different orders can be run at the same time or can overlap in time. For example job 3 of order 3 can be run simultaneously with job 1 of order 2. There are also setup times that is connected with each order.

Fig. 5 shows a population of 10 production plans. With each production plan, a make-span is connected. The Binary Tournament Selection was adopted here for the selection process. Very good results are connected with this type.