1. Introduction

Recently, improvement of production efficiency on cars manufacturers is required owing to increasing of demands in developing countries. On the other hand, that improvements under existing circumstances are depending on experience and intuition by workers at a production line^{1, 2}. To overcome this situation, we propose to objectively and efficiently improve a production line without depending on experience and intuition. The production line of candidate for optimization is “Picking up assemblies” area, so that our aim is to optimize the positions of racks and boxes for assemblies. The difficulty of optimization of “Picking up assemblies” area is that the number of racks to put assembly boxes and that boxes is predetermined.

Our optimization problem is similar to several path planning problems such as “Traveling Salesman Problem (TSP),” “Minimum Spanning Tree problem(MST).” Workers pick up assemblies while they goes back and forth between racks and an AGV. Accordingly, our optimization problem becomes synonymous with minimization of total length of moving path of a worker. The difference between path planning problems and our problem is that positions of waypoints for path planning problems are fixed; on the other hand, our problem changes positions of waypoints that are racks and boxes.

Since the number of racks and boxes is predetermined as mentioned, our approach has to put predetermined number of racks and boxes into a production line. For this, there is also a problem of “Knapsack Problem(KP)” in our optimization problem. It can be said that our optimization problem combines TSP, MST and KP for the reasons stated above.

To overcome difficulties, we propose to apply a Genetic Algorithm(GA)^{3, 4} to optimization for positions of racks and boxes. A GA is suitable for global search in a high dimensional space because a GA has also the ability of probabilistic random search based on genetic operations in addition to local search. A GA has many individuals(populations), and an individual has a chromosome that cords the parameters for optimization. Optimization processes are on the basis of genetic operations, i. e., selection, crossover and mutation. A process of crossover and mutation does not be constrained because parameters for optimization in a chromosome are independent in each; therefore, generated parameters of optimization are able to take all values within a set condition. By contrast, parameters of optimization in our problem are dependent on each other because the number of racks to put assembly boxes and that boxes is predetermined. Consequently, we are not able to apply a conventional GA to optimization. For this, we apply a “constrained GA” to optimization for positions of racks and boxes in a production line.

The details of our constrained GA are below. Gene loci correspond to racks and boxes positions in a constrained GA. Selection process in genetic operations is same way as a conventional GA. In crossover process, loss or duplication of some racks and boxes will occur. The way of adjustment of the number of racks is that all of duplicative racks are deleted then missing racks are randomly inserted to those positions. Mutation process for racks is executed after the adjustment of crossover process. Mutation process in a constrained GA changes gene loci in order to meet the conditions for the number of racks. Crossover and mutation process for positions of boxes in racks is executed after crossover and mutation process for racks. Crossover process for boxes is executed on the same stage each other, e.g., boxes in top stage of a rack are changed with boxes in top stage of another rack. In mutation process, genes for boxes are mutated randomly as same as a conventional GA in first. Following that, excess boxes are randomly chosen, then those boxes are deleted. Subsequently, shortfall in boxes are inserted randomly to meet the conditions for the number of boxes. From a constrained GA in above, our proposal is able to meet the conditions for our optimization problem.

The results of simulation for virtual production line show that our proposal succeeded in reducing about 10 seconds per a car compared with random positioning.

2. Virtual Environment of Production Line

We construct a virtual environment of production line to validate the effectiveness of our proposal. Table 1 shows the conditions for virtual environment, and Table 2 shows the number of assembly boxes for each car.

A worker in virtual environment picks up the all of assemblies which correspond to a designated car in the Table 2. Besides, 20 shared assemblies are randomly designated from the all of shared assemblies.

The Fig. 1 shows the bird’s-eye view of an example of virtual production line. The condition in that figure is initial state of picking up assemblies. A worker goes back and forth between racks and an AGV. An AGV moves at a constant speed on a lane.

Fig. 1.

Bird’s eye view of an example of virtual production line. Values are distance and size of rack. Unit is millimeter. The red circle indicates a worker. The blue, yellow and magenta squares correspond to 1000, 1500 and 2000 size of racks, respectively.

Consequently, our optimization problem is same as minimization of the moving distance of a worker.

3. Optimization Problem

From the above section, our optimization problem is similar to several path planning problems such as “Traveling Salesman Problem (TSP),” “Minimum Spanning Tree problem(MST).” Our optimization problem becomes synonymous with minimization of total length of moving distance of a worker. The difference between path planning problems and our problem is that positions of waypoints for path planning problems are fixed; on the other hand, our problem changes positions of waypoints that are racks and boxes in order to minimize length of moving distance.

In addition, since the number of racks and boxes is predetermined as mentioned in the table 1 and 2, our approach has to put predetermined number of racks and boxes into a production line. For this, there is also a problem of “Knapsack Problem(KP)” in our optimization problem. It can be said that our optimization problem combines TSP, MST and KP for the reasons stated above.

4. Genetic Algorithm and Constrained

To overcome difficulties mentioned in the section 3, we propose to apply a GA to optimization for positions of racks and boxes. We explain the details of a conventional GA, and of a constrained GA to solve our problem.

5. Experiments

In this section, we validate the effectiveness of a constrained GA for optimization of a production line. The parameters for a constrained GA are shown in Table 3. The fitness function is as the Eq. (1).

where i is individual number, t_j is total time of picking up of all of assemblies for car j, N_E is the number of evaluation cars for an individual.

Fig. 4 illustrates the changes in the fitness value of the best individual. Positions for racks and assembly boxes are randomly determined in the first generation; therefore, the maximum time for picking up in the first generation is about 70.9 second and the minimum is about 65.3 second.

Fig. 4.

Optimization results. “Blue line” shows “Case 1” and “Orange line” shows “Case 2” in Table 3.

In contrast with the first generation, the time for picking up assemblies from the optimized positions in last generation is about 61.7 second from Fig. 4. For this, our proposal achieved to reduce about 10 seconds per a car compared with random positioning.

6. Conclusions

We propose to optimize a production line of cars manufacturing plant by GA in this paper. The difficulties of our aim are that parameters of optimization in our problem are dependent on each other because the number of racks to put assembly boxes and that boxes is predetermined. Consequently, we are not able to apply conventional GA to optimization. For this, we apply a “constrained GA” to optimization for positions of racks and boxes in a production line.

From the results of experiment, our proposal achieved to reduce about 10 seconds per a car compared with random positioning.