De-kai XU, Li-jie WANG, Wei-chao SHI

(Higher Institute of Technology, Xi’an University of Technology, Xi’an 710082，China)

?

Research on flexible manufacturing system real-time scheduling optimization

De-kai XU*, Li-jie WANG, Wei-chao SHI

(Higher Institute of Technology, Xi’an University of Technology, Xi’an 710082，China)

The main problem is the scheduling of AGV in real-time scheduling optimization of the FMS logistics system. This paper presents two forms of AGV scheduling strategy, one is based on genetic algorithms (GA) of the AGV scheduling, the other is based on particle swarm optimization (PSO) of the AGV scheduling. It verifies the model and scheduling optimization ideas by example based on the developed simulation program and the scheduling module. According to the running of the real-data of assumption, the processing time of the FMS is shortened by real-time scheduling optimization.

FMS, Real-time scheduling, GA, PSO

1 Introduction

Flexible manufacturing system (FMS) is increasingly valued by producers and becomes the mainstream of modern production methods. Today the core of the FMS production logistics scheduling focuses on the workpiece scheduling, machine scheduling, vehicle scheduling and warehouse scheduling, this research is mainly on the scheduling for automated guided vehicle (AGV).

Scheduling is to allocate scarce resources to the different tasks within a certain time. It is a decision-making process and the aim is to optimize one or more targets [1]. Scheduling technique is one of the key technologies to determine whether the entire FMS can achieve the expected economic benefits. The scheduling algorithm has been inseparable with optimization since its appearance, because the purpose of research on scheduling is to improve the system operating efficiency, which just reflects the optimization.

Two forms of AGV scheduling strategy are briefly described in the article: the AGV scheduling based on the genetic algorithm (GA) and the AGV scheduling based on particle swarm optimization (PSO). By verifying the model and scheduling optimization thought with specific instances, integrating the scheduling module based on the already developed simulation program, and from the real-time operating assuming processing task data, it is proven that the completion time of the system tasks after real-time scheduling optimization is significantly shortened and the task processing efficiency of the system improved.

2 Genetic algorithm

Genetic Algorithm (GA) is a algorithm based on the principle of natural selection, the natural genetic mechanism and the self-adaptation search, which is an important branch of contemporary artificial intelligence science, and it provides an effective new way to solve many traditional math problems and complex problems failing in routine conditions, so as to bring new prospects for the development of the research on the artificial intelligence computing theory, so it has become an emerging discipline in the field of information science.

2.1 GA thought

GA starts from a population of the problem with possible potential solutions, but a population consists of some individuals of the synthetic gene encoding, each individual is an entity with chromosomal features. As the main carrier of inheritance, i.e., a collection of genes, chromosome is a combination of a gene inside and determines the external representation of individual features. Thus, the state space of the problem to solve needs mapping as genetic space at the beginning. In GA, each possible decoding and encoding is taken as vector, each element of the vector is called the gene, and all of the chromosomes are formed into groups, each individual is evaluated according to the given objective function, the individual is selected the according to the fitness values given by the objective function value, and crossover combination and mutation are conducted by simulating the principle of natural genetics to produce a population that can represent a new solution set. This process will make the epigenetic generation population more adaptive to the environment than the previous generation of the population like the natural evolution, and the best individual of the last generation of population after decoded can be taken as the approximate optimal solution of the problem [2-4].

2.2 GA implementation process

In solving FMS scheduling optimization problem, comparison sorting will be conducted on the objective function value of individuals, based on which the selection probability is determined, so the objective function must be non-negative; in addition, in the later stages of genetic evolution, diversity of population reduces, there may be individuals inherited to the next generation with similar probability, so that it evolves into a random selection process, which will largely affect the performance of GA. In this paper, linear scaling method is used to map the objective function value for a real value in order to avoid premature of GA. Implementation process of the algorithm is shown in Fig.1.

3 Particle swarm optimization

Particle swarm optimization (PSO) is a kind of bionic intelligent algorithm [5-6], and it uses prey behavior of birds to get the optimal solution through iteration. In this paper, in the scheduling of FMS logistics organization, the algorithm is treated correspondingly to be applied and to play its advantage in the scheduling, iteration process of the algorithm is relatively simple compared with the GA, but the algorithm has higher optimizing speed and has achieved better optimization results.

Fig.1 Self-adaptive GA flowchart

3.1 Algorithm flow

The principle of PSO can be simply stated as: each bird (particle) in the optimal position get closer to food destination step by step by tracing a finite number of neighbors in the current optimal position. From the optimization thought of the PSO it can be seen that each particle flies close to the optimal value step by step by velocity-position relationship calculation, its workflow is shown in Fig.2.

PSO also shows its superiority compared with other intelligent algorithms, in the optimization experiments of a unimodal function and a multimodal function, PSO is better than the evolutionary strategies in the optimization efficiency, the computation time and impacts by population number, the initial population and other parameters. For instance, the 1000th generation of evolutionary strategy can achieve function value precision of 0.0001, and the 278th generation of particle swarm can achieve precision of 0.000 001.

Fig.2 Work flowchart of PSO

3.2 Implementation process

The real-time scheduling strategy proposed here is: dynamic scheduling based on PSO, and based on the PSO, this paper uses the three-dimensional vector coding method, the method of first decoding and then calculating the objective function by reading meter and the method of floating and searching for the objective function, so that the PSO can be used in a particular AGV queue dynamic optimization occasion. Scheduling of dynamic AGV is completed in accordance with the process as shown in Fig.3.

4 AGV scheduling optimization instances

Use a specific production instance to verify optimization results of the two real-time scheduling strategies, as well as the consistency of the program execution state and the actual state of the production process flow.

Hardware size of the instance is the number of devices considered in the system design, which is just a small FMS processing system consisting of four sets of CNC machining center devices (with machine magazine), two AGVs, and a stereoscopic warehouse of the automated single-stacking machine. This arrangement state determines the operating time of AGV in the device room, the “AGV Operating Schedule” is saved in the file folder where the simulation program is, so that the scheduling part can read this ACCESS file to calculate, optimize and provide AGV transportation time during simulation operation.

Fig.3 Flow diagram of dynamic scheduling optimization and calling of AGV queue to be transported

The small FMS with the above layout can complete multitasking machining operations, and the machining tasks in the instance are set to 6. In the equipment operation time and data of processing document determined by hardware layout, start the system simulation program, first load the data, and then call in the scheduling optimization, run the simulation program. Choose a random moment in the simulation program operation (such as the 360th s) to track and record the status data of FMS logistics system at this moment during its operation, and conduct comprehensive analysis and comparison of the operation results.

Fig.4 is a part of the diagram of operating instance.

In the instance, after the processing task is optimized by the AGV transport part, completion time of the entire batch of task is significantly shortened, and the operating time data of its various parts after the simulation operating is completed is recorded and shown in Table 1.

Fig.4 Part of the diagram of operating instance

Table 1 Comparison of the simulation results in various scheduling methods

SchedulingformAlge-braAGV1/(time·s-1)AGV2/(time·s-1)Systemcompletiontime/(time·s-1)Nooptimization(equalprobabilitydistribution)0126614881616GA50130214561564GA100142113981480PSO50140414021476PSO100136013541420

By longitudinal comparison of Table 1 it can be seen: when the FMS system has no optimization, the total time to complete six workpieces is 1616 seconds; after optimizing task scheduling of AGV in GA, the total completion time of the system is significantly shorter than that before optimizing, it is shortened by 3.2% at the 50th generation, and by 8.4% at the 100th generation; after PSO dynamic real-time optimization, AGV task queue is optimized in real time, and the time is also significantly shortened compared with that before optimizing, it is shortened by 8.7% at the 50th generation, and by 12.1% at the 100th generation, which shows the outstanding results of PSO.

And by horizontal comparison of Table 1 it can be found: tasks of the two AGVs are well matched after optimizing, the difference in time of the two AGVs before scheduling optimization is 222 seconds, indicating that even though the number of transportation tasks is equal after the task equiprobability assignment, time of different transport tasks is different, resulting in large difference in AGV operation, the tasks are not matched and it also indirectly makes the overall completion time of the system longer; and the total time of transport of two AGVs only has six seconds difference after PSO, and the largest difference after the program runs for ten times is only 48 seconds, the evenness in task allocation is better than GA, showing that balanced use of different AGVs is good for use and maintenance of AGV.

5 Conclusions

In this paper, research is carried out with FMS system as the subject and improvement of the efficiency of FMS logistics as the goal, it mainly studies real-time scheduling optimization of AGV transport queue in GA and PSO; FMS logistics system is simulated with the system simulation program to verify correctness of the model and effectiveness of scheduling optimization. And through simulation running data, the effects of scheduling in GA and PSO can be clearly seen by comparison so as to select the appropriate scheduling method to be applied in the actual production system in the future.

[1]Pinedo M. Scheduling: Principles, Algorithms and Systems [M]. Beijing: Tsinghua University Press, 2007.

[2]Chen Lunjun, Luo Yanke. Genetic Algorithm of Mechanical Optimal Design [M]. Beijing: Mechanical Industry Press, 2005.

[3]Xuan Guangnan, Chen Runwei. Genetic algorithm (ga) and engineering design [M]. Beijing: Science Press, 2000.

[4]Zhou Ming, Sun Shudong. Genetic algorithm principle and application [M]. Beijing: National defence industry Press, 1999.

[5]Liu Zhixiong. Research on Particle Swarm Optimization and its Application in Scheduling [D]. Wuhan University of Technology. 2005.10.

[6]Bian Peiying, Li Dexin, Bao Baojun. Research on Application of Particle Swarm Optimization in Production Logistics Scheduling [J].Computer Engineering and Applications, 2010,46 (17): 220 - 223

(Continued on 51 page)

13 January 2015; revised 4 April 2015;

De-kai XU, Lecturer.

E-mail: 452763124@qq.com

10.3969/j.issn.1001-3881.2015.18.008 Document code: A

TH162

accepted 11 May 2015

Hydromechatronics Engineering

http://jdy.qks.cqut.edu.cn

E-mail: jdygcyw@126.com