Production scheduling optimization method based on hybrid particle swarm optimization algorithm

2.1 Particle swarm optimization algorithm

At the end of last century, particle swarm optimization algorithm was proposed for the first time. This kind of artificial intelligence algorithm is a kind of imitation of birds in the process of searching for food in nature. Each individual particle swarm is set with velocity and position parameters similar to the birds move, and its diversity can be ensured by changing the particle velocity and position in the process of evolution [5]. When the iteration is performed, the information of the particle and other particles is compared, so as to find the best mobile solutions which can meet the end conditions [6]. If it does not find the optimal solution, it will continue to evolve until the output particle. In addition to its own speed and position parameters of each particle, there is a value of the fitness for each particle. This value can be used to judge the good or bad particle. In the process of evolution, the choice of the best particle is the evolutionary process. The particle is constantly updated to compare itself with the optimal particle. Assuming that c₁ and c₂ is, respectively, the acceleration factor of the best particle selected from the overall situation and the individual, w is the inertia factor, rand₁ () and rand₂ () are the random numbers during the interval [0, 1], and the update rate of the particle is:

v id ( t + 1 ) = w × v id ( t ) + c 1 × rand 1 ( ) × [ pbest id ( t ) - x id ( t ) ] + c 2 × rand 2 ( ) × [ gbest id ( t ) - x id ( t ) ](1)

Using the dimension vector D to represent the particle’s individual information, the position of each particle is expressed as X _i  = (x_i1,  x_i2, ⋯,  x _id ), and the formula for the particle to update its position is: x id ( t + 1 ) = x id ( t ) + v id ( t + 1 )(2)

In formula (1), the acceleration factors of c₁ and c₂ are relative to the key. When the values are relatively small, it will cause the short particle’s moving distance, and it is difficult to obtain qualified particles. When the values are larger, it will be too far away from the particle flight distance and make it easy to deviate from the target area. According to previous studies, it is easier to obtain the qualified particles when the selected value is 1.

The algorithm flow of particle swarm algorithm is as follows. (1) To initialize the parameters such as the velocity and position of the particle, and the initial parameters are randomly generated in the space of the solution. And the initial parameters are set up to set the global and the extreme value of the particle. (2) The velocity and position of the particle are updated, and the extreme value is compared with the set value. If it is in accordance with the requirements of evolution, the particle information and the global extremum are transformed. Otherwise, the conversion of particle information and individual extremum will be made. (3) To update the velocity and position of the particle in the solution space, continue to search for the updated particles as the new particles. The updated particles are used as the new particles, and the following steps are repeated to carry out a round of evolution. (4) Each evolution is compared that whether particles can meet the maximum number of iterations set. If the algorithm satisfies the algorithm, the optimal particle will be output. Otherwise, repeated cycle steps are needed until the optimal solution is obtained [7]. The basic algorithm flow of particle swarm is shown in Fig. 1.

OPEN IN VIEWER

Fig.1

The basic flow chart of particle swarm optimization algorithm.

For the particle swarm algorithm, the most important is to select the appropriate parameters as the standard. Only in this way can we obtain the optimal solution in the higher efficiency [8]. The first step is to choose the appropriate particle size. When the particle size is larger, the number of particles can be selected more, and it is easier to obtain the optimal solution. But the corresponding calculation will become large, and generally forty or so particles are more suitable. Within the allowable range, the length of the particle determines the information contained in its evolution process, so it should be as long as possible. In the evolution of the particle, it is necessary to select the appropriate fitness function. Only when the particle meets the requirement, it can stay [9]. The trajectory of the particle is not controllable, and its speed is random variable. The greater the maximum speed, the more conducive to the control of particles. But when the step length is too short, it is possible to get the local optimal solution. When the velocity is too large, it is difficult to obtain the particle motion law, which can make the algorithm in a state of stagnation, but can’t get the optimal solution [10].

Genetic algorithm is a kind of imitation of biological survival of the fittest in the natural environment, and it is a kind of evolutionary algorithm based on the rule. In the running process of genetic algorithm, we must first determine the population size, set the fitness function based on the actual needs, complete the selection operation, crossover operation and cycle operation, and finally find the optimal solution [11]. Because the genetic algorithm has better global search ability, it has a good effect in solving many complex search problems, which is widely used in each process of the production [12]. Especially in the aspect of job shop scheduling problem, genetic algorithm has obvious advantages. Since it is from the population of individuals, the scope of the evolutionary algorithm covers the entire population. Searching for the optimal solution is in the whole global range, and the final solution is more in line with the actual requirements [13]. Because the genetic algorithm has some parallel processing ability, it can deal with the individual in many groups at the same time. Because the way of the probability is used in the search, the search efficiency is higher. According to the situation, the fitness function can be set free in the early stage, which will not be affected by other factors. The search does not need to rely on other information, and the fitness function can be used to obtain the individual assessment value, thus expanding its application space. However, the optimal solution may not be found in the global scope because of the unreasonable fitness function in the early stage [14]. On the other hand, when the population size is relatively small, even though it is easy to obtain the optimal solution, it may not be the desired solution. When the population size is large, it may be because the search scope is too large and it takes a long time to search, resulting in excessive consumption of resources. In order to make up for the shortcomings of the slow speed of genetic algorithm, it can be combined with other algorithms, so that it can have a higher evolutionary efficiency [15]. The specific steps of genetic algorithm are shown in Fig. 2.

OPEN IN VIEWER

Fig.2

The basic process of genetic algorithm.

OPEN IN VIEWER

Fig.3

Sketch map of flow shop scheduling.

It can be seen from Fig. 2 that the steps of the genetic algorithm are preliminary coding, population initialization, selection operation, crossover operation, mutation operation and loop and getting the final optimal solution. Because the genetic algorithm needs to be modeled on the laws of nature, it is necessary to implement the code in accordance with certain rules. Coding data structure is the chromosome, and the chromosome can be converted into a solution space, which is the decoding process [16]. Encoding and decoding are also very important steps in genetic operation, which can obtain the optimal solution and reduce the waste of resources. The chromosomes get together to form the population, and the process of population initialization is to determine how many chromosomes. After setting the fitness function of the genetic algorithm, the individuals who are poor in quality will be eliminated from the population, and the excellent individuals are selected. Through the selection of the operation, the fine individual can genetic to the next generation, so as to achieve evolution [17]. Two pairs of paternal genes are randomly selected, and then the new chromosomes are exchanged. The crossover operation not only can increase the population diversity, but also can expand the search scope, so as to improve the search speed, and solve the optimal solution in a faster time. Mutation operation is a random selection of individual genes on the chromosome, and makes it transformed, thus ensuring the diversity of chromosomes. So in the case of retaining the original genetic information, new genes can be obtained, so that the population towards a better direction of development [18]. In actual operation, the maximum number of iterations is artificially set, and the algorithm will not be terminated until the algorithm runs to the maximum number of iterations. Therefore, we need to set up a reasonable maximum number of iterations, to prevent too much computation.

Because of the various characteristics of genetic algorithm, it has a very wide range of practical applications. As long as objective function and fitness function can be set in the evolutionary process, it will not affect the external factors. It is widely used in combinatorial optimization problems, neural network, image processing, job shop scheduling, pattern recognition, artificial life, data mining and other aspects [19].

3.1 Flow shop scheduling

Flow shop scheduling problem entered the people’s vision at the beginning of the last century. After several decades of research and development, the theory of job shop scheduling had been studied in a certain degree. However, until 1970s, the algorithm theory of the flow shop scheduling problem had been discovered which can be directly applied to the production practice. With the continuous development of science and technology, the requirement of flow shop scheduling is also higher and higher, and the traditional scheduling algorithm has been difficult to meet the growing demand for production [20]. The commonly used scheduling algorithms include heuristic scheduling algorithm, the artificial intelligence method, neural network algorithm, and Lagrange relaxation method. Different methods have their own characteristics and adapt to different job shop scheduling problems. There are many problems in job shop scheduling, According to the complexity of the flow shop processing, the number of the artifices and the line, the characteristics of the production environment and the characteristics of different processing tasks, the problem is also complex and diverse. Therefore, the flow shop has a certain complexity and multiple constraints. In the actual production scheduling process, enterprise management will take into account the production cycle, machine load and delay time and other factors. These factors have mutual relation and restriction, which requires the enterprise to carry on the comprehensive regulation to the goal, and optimize the multiple objectives at the same time. In the production scheduling process, the production of the artifices not static, and it may be affected by equipment failure, cancellation of orders and other factors, making the production scheduling problem more complex.

Taking the mixed flow shop as a typical example, the processing sequence should be determined before the artifices processing. Because each process of the machine is different, it is different to balance all aspects. But in the modern production environment, hybrid flow shop scheduling problem is more and more in the modernization of production and manufacture. Assuming that the artifice processing lines are in the same direction, and each process may have more than one parallel machine. The artifices can be stored between the processes without the number of restrictions. The processing of two processes can be carried out at any time. And the process is shown in Fig. 4.

OPEN IN VIEWER

Fig.4

Sketch map of flow shop scheduling.

Each department of the enterprise has different requirements for production scheduling because of different goals, so the key problem of production scheduling is to make it possible to achieve the best, such as the production workshop can get a higher production rate, and the sales department can complete the contract in time. Assuming that all the machines are working normally at the beginning of the process, all the parts can be processed normally; At some point, the same artifice can only be processed on one machine, without considering the damage to the machine; The sequence and time of the artifice is fixed, and the machining process cannot be interrupted; The processing time includes the preparation and delivery time of the artifice. In the process of production scheduling, the time required for the completion of the artifice is called the scheduling cycle. The smaller the value is, the better the effect of scheduling is. The production cycle of the artifice J _j is C _j , and then the minimum period of the objective function is calculated as: f 1 = max C j(3)

The enterprises need to carry out the contract for the production and delivery of goods, and it cannot exceed the delivery period, otherwise it may compensate very high default payments for the customer’s. Once the delivery period is exceeded, in addition to the high default payment, it will seriously affect both the credibility of enterprises and the customer’s production. So the delivery time is a very important factor in the production scheduling. The delivery time is set to be d _j , and the trailing time of each artifact is Max [C _j  - d _j ,  0]. And the total drag period of time can be drawn: f 2 = ∑ j = 1 N max [ C j - d j , 0 ](4)

The time required for the i work on the k machine is t _ijk , and the decision variables for whether to choose for processing are X _ijk . The working load of M _k is W _k , then the utilization ratio of the equipment is expressed as: f 3 = ∑ k = 1 M W k = ∑ k = 1 M ∑ j = 1 N ∑ i = 1 n j t ijk X ijk(5)

The maximum load of a single machine is further calculated: f 4 = max 1 ≤ k ≤ M W k = max ∑ j = 1 N ∑ i = 1 n j t ijk X ijk(6)

In order to achieve the optimization of hybrid flow shop scheduling, it is needed to meet the minimum based on the formula (3), (4), (5), (6) to, and further apply it to the shop scheduling model: Miny = f ( x ) = { f 1 ( x ) , f 2 ( x ) , ⋯ , f n ( x ) }(7)

From the formula (7), it can be seen that the flow shop scheduling problem has not only a unique optimal solution, and it needs to make optimal selection and adjustment from multiple objectives according to the actual situation.

The genetic algorithm has the characteristics of simple encoding and relatively simple evolution process, and it can search the optimal solution in the global scope, which can effectively solve the combinatorial optimization problem of production scheduling. However, it also has the problem such as the low efficiency and premature convergence. Particle swarm optimization algorithm has the characteristics of simple calculation and high efficiency, which can be directly used to screen out good individuals to guide the direction of the next generation of particle evolution. But it is easy to fall into the local search and the easy early maturity of improvement. In order to make the respective characteristics of particle swarm algorithm and genetic algorithm complementary, give full play to each other’s advantages, the two algorithms are combined to obtain the hybrid particle swarm optimization algorithm, and it is applied to flow shop scheduling.

The hybrid algorithm is to code based on the process and machine, and the 2Z dimension vector is used to better solve the mapping relationship between the position vector and the scheduling scheme. It not only uses the high efficiency of particle swarm optimization algorithm, but also uses the global optimization ability of genetic algorithm. The selection operation is completed through the championship and the way of retaining the best individual, and the crossover operation uses the improved cross method and multi point crossover operation. After the optimal solution is obtained, the relatively poor individual in the particle swarm is replaced, and the search area is further expanded. The individual is migrated to each particle swarm, and finally the optimal solution is obtained through the reciprocating cycle. The structure diagram of the hybrid algorithm is shown in Fig. 5.

OPEN IN VIEWER

Fig.5

Structure diagram of hybrid particle swarm optimization algorithm.

The specific process of the hybrid particle swarm optimization algorithm is shown in Fig. 6. It can see from Fig. 6 that the successive process of hybrid algorithm contains encoding, initialization parameters, the generation of initial individual group, particle individual decoding, generating weights, calculating fitness, particle swarm search, individual migration and substitution, calculating fitness of genetic algorithm, genetic algorithm operation, individual migration and substitution, and final judgment of termination conditions. When the optimal solution is obtained, the calculation is terminated. If it is not obtained, the search will continue.

OPEN IN VIEWER

Fig.6

The basic flow chart of hybrid particle swarm optimization algorithm.