Research On Limit Buffer Of Flexible Flow Shop Scheduling Problem Based On EM Algorithm

Limited buffer flexible flow shop is an extension of flexible flow shop,and it is the combination of flexible flow shop and the real manufacturing,which widely exists in the important fields of the national economy including the vehicles manufacturing,tobacco,semiconductor production and large equipment manufacturing.The main feature of limited buffer flexible flow shop is that the buffers exist between the processes and the capacity of the buffers are limited.When a job is finished on the current machine and if the next process is occupied,the job enters into the buffer for waiting.The number of jobs in the buffers between the adjacent processes in the flow shop is strictly limited due to the low level of technology and the constraints on the storage equipment and the production process.When the buffers are full,the job will wait on the current machine until the buffers become free.The capacity of limited buffer leads to the blocking problems.So the limited buffer flexible flow shop scheduling problem is a NP-hard problem,which is more complicated than JSP.The order of the job in the buffer is related to the production efficiency of enterprises.In addition,with the diversification and individuation of the market demand of various products,the workshop not only has large production tasks,but also has a large number of production tasks,which inevitably leads to difficult control of the production line rhythm and increased uncertainty of the production process,these factors will lead to increased demand of buffer in production process,to ensure the work shop complete the task efficiently.The content of this paper has an important theoretical significance and practical application value.Limited buffer of flexible flow shop scheduling problem(LBFFSP),is added the limited buffer to the flexible flow shop scheduling problem,which makes the problem more complicated.An in-depth study on limited buffer flexible flow shop scheduling problem is done in this thesis.At first,the limited buffer flexible flow shop mathematical programming model is established.According to the first in first out(FIFO)principle and the first available machine(FAM)principle,we consider the occurrence of station blocking in the decoding process.In order to facilitate the representation,a hybrid heuristic decode method(HDM)is used to establish the mathematical programming model.Then the limited buffer flexible flow shop scheduling process is analyzed,after that an in-depth study on the optimization method of the limited buffer flexible flow shop production scheduling is done.Electromagnetism-like mechanism algorithm and its improved algorithm are taken as the global optimization algorithm of limited buffer flexible flow shop scheduling problem which have simple structure and strong global optimization ability in this thesis.The main steps of EM algorithm included initialization,local search,calculation of electric charges and resultant force,and particle movement.Meanwhile,EM algorithm can also be combined with other algorithms to form a new combination algorithm to improve the performance of the algorithm.The optimization target is to minimize makespan.The classical electromagnetism-like mechanism algorithm is used to solve the limited buffer flexible flow shop scheduling problem at first,and the effectiveness of the algorithm can be verified.However,the EM algorithm also has many shortcomings.In the local search strategy,the random search is used.The searching range of EM algorithm is small and it is easy to fall into the local extremum,so the algorithm can't find the global optimal point,the population diversity of the algorithm also gradually decreased with the iterative process,which easy to make it difficult to jump out of the local extreme,resulting in algorithm accuracy is not high.So we need to improve the EM algorithm,so that the algorithm in the solution of various types of complex problems are highly efficient,robust and stability.In order to overcome the shortcomings above,this paper introduces the idea of simulated annealing.In the local search step of EM algorithm,the simulated annealing algorithm is combined with the annealing operation to accept the solution which makes the objective function value worse with a certain probability,This can enlarge the searching range of the algorithm,and increases the diversity of population particles,improves the flexibility of the algorithm,and effectively avoids the algorithm getting into the local optimal solution in the iterative search process,thus increased the ability and precision of the algorithm to search the optimal solution.This improved method just to make up for the shortcomings of the standard electromagnetism-like mechanism algorithm.In addition,because of the initial population of EM algorithm is randomly generated,and the quality of generation is not high.In this thesis,an establishment method of the initial population based on the probability model is raised which can improve the species richness and improve the whole evolutionary convergence speed.Probabilistic model-based methods can increase the randomness of each individual,making the resulting individuals closer to the optimal solution,the evolutionary effect is better,and the minimize maximum completion time is used for the optimization goal to establish the probability,which makes the generated individuals closer to the optimal solution,evolutionary effect is better,and thus improve the global optimization effect.In this thesis,the main work of this paper is to improve the performance of electromagnetic-like algorithm itself and apply the improved algorithm to real complex production scheduling problem.The improved electromagnetic-like mechanism algorithm is superior to the classical electromagnetic-like mechanism algorithm in the optimization precision and the convergence speed.The improved algorithm is effectively avoiding into local extreme.The algorithm will be further researched in the subsequent works.