The Research On Scheduling Problem Of Re-entrant Hybrid Flow Shop

Hybrid Flowshop(HFS)has many tasks,various processes,multi workstations,different processing time of jobs in the same working procedure.When there is Re-entrant lines in the Hybrid flow shop,the manufacturing process is more complicated,the production load is doubled,and the load imbalance of the equipment is increased,which greatly increases the difficulty of scheduling the Hybrid flow shop.Re-entrant Hybrid Flowshop Scheduling Problem(RHFSP)is a typical NPhard problem.At the same time,RHFSP scheduling optimization problens are widely found in key industries such as semiconductor production,bus manufacturing,and steel smelting.Due to the constraints of the actual production workshop space and storage equipment,only buffers with limited capacity can be set on the production line.The re-entrant hybrid flow shop has the feature that the job that performs the re-entrant working procedure needs to be re-entered into the waiting match area to be processed.When the job is folded back to perform the re-entrant working procedure,the buffer resource is competed with the job that has been completed in the previous working procedure,and the influence occurs.The deadlock phenomenon of the entire production process.In the case where the buffer resource is limited and the reentrant working procedure exists at the same time,the deadlock phenomenon will have a serious impact on the production process,which further aggravates the uncertainty of the production process and greatly increased the difficulty of scheduling of the enterprise.Therefore,the study of the Limited Buffer Re-entrant Hybrid Flowshop Scheduling Problem(LBRHFSP)solution with re-entrant working procedure has important theoretical and engineering application value.In this paper,based on the scheduling problem of LBRHFSP,a mathematical programming model of limited buffer in Hybrid flow shop with re-entrant working procedure is established,and a scheme for solving LBRHFSP scheduling problem is proposed.When the job is folded back to perform the re-entrant working procedure,a deadlock phenomenon occurs when the buffer is competed with the job that has been completed in the previous working procedure.If the buffer can reserve capacity in advance for the job that performs the reentrant operation,the job can re-enter to the limited buffer,thus reducing the probability of deadlock in the production process and ensuring the progress of the production process.Therefore,a dynamic re-entry buffer capacity reservation based on Markov chain is proposed.The method ensures that the scheduling process goes smoothly under the condition that the re-entrant working procedure and the limited buffer are both present.At the same time,a local optimization method based on high response ratio priority scheduling strategy is adopted to make the assignment of jobs at the workstation more reasonable in the local assignment process,which further reduces the probability of deadlock phenomenon.The variable neighborhood search wolf pack algorithm based on opposite learning initial population strategy is used as the global optimization method.Combined with the local assignment method and the buffer capacity dynamic reservation method,a scheme for LBRHFSP scheduling problem is presented.The specific research content of this paper is as follows:(1)Establish a mathematical programming model for LBRHFSP scheduling optimization problemThe model elements of the re-entrant working procedure are added on the basis of the Hybrid flow shop,and the constraints of the limited buffer are introduced.The mathematical programming model of the limited buffer scheduling problem of the Hybrid flow shop with reentrant working procedure is given,and the mathematics is applied.The language describes and analyzes the deadlock caused by the artifacts competing for buffer resources during the production process.(2)Research on global optimization method for LBRHFSP scheduling optimization problemThe Wolf Pack Algorithm(WPA)has the advantages of faster convergence and higher precision than other intelligent evolution algorithms.Therefore,the wolf pack algorithm is used as a global optimization algorithm to solve such complicated scheduling problems.At the same time,the wolf pack algorithm also has the characteristics of being easily trapped in local extremum.In view of the shortcomings of wolf pack algorithm,this paper proposes four methods to improve the algorithm:? A scouting behavior based on Levi's flight is proposed,which enables the wolves to explore the search area with small probability,expand the search range?and improve the search ability of the wolf pack algorithm.?A dynamic update mechanism based on Hamming distance is proposed.When the iteration of stagnation exceeds the threshold,the similarity among individuals is judged by Hamming distance,and the individuals with high similarity with the leader wolf are eliminated.New individuals with low similarity enrich individual diversity and enhance the ability of the algorithm to jump out of local extremum.?This paper proposes a scouting behavior based on variable neighborhood search,which uses the neighborhood structure composed of different actions to perform an alternate search,so that the wolves explores the small probability search area by alternating search mode which expands the search range.Enhance the search performance of the algorithm in the solution space and further enhance the evolutionary vitality.?In order to further improve the algorithm optimization speed,the population initialization strategy based on opposite learning is adopted to expand the search range of the initial solution in the solution space,and to determine better individuals as initial individuals,improve the initial solution quality,and accelerate the optimization process.Based on the above four improved methods,this paper proposes a dynamic wolf pack algorithm based on Levy Flight(LDWPA)and a variable neighborhood search wolf pack algorithm based on opposite learning initial population strategy(Opposition-based Learning Wolf Algorithm Based on Variable Neighborhood Search,OLVWPA)Two new improved wolf pack algorithms are available to better solve the LBRHFSP scheduling problem.(3)Research on deadlock problem in LBRHFSP schedulingIn order to solve the deadlock phenomenon in the process of re-entrant hybrid flow shop with limited buffer,a dynamic reservation method based on Markov chain for buffer capacity is proposed.By predicting the job will be folded back to the job that is processed in the re-entrant working procedure,that is,the probability of the corresponding buffer resource are released,the capacity of the buffer for the job that performs the re-entrant operation is dynamically reserved during the scheduling process.so that the job can be re-entered into the limited buffer,reduce the impact of continuous blocking on the production process due to the contention of the buffer resources,and reduce the probability of deadlock phenomenon in the production process,thus ensuring The scheduling process can proceed smoothly.(4)Optimization design of LBRHFSP scheduling problemBased on the above research results,a scheme for LBRHFSP schedul,ing problem is proposed.The Markov chain-based limited buffer capacity dynamic reservation method is adopted to reduce the probability of deadlock and ensure the smooth progress of the scheduling process.On this basis,the optimization method of the scheduling problem is explored.By comparing the four improved methods of wolf pack algorithms proposed in this paper,the global optimization method is determined by the OLVWPA algorithm.The local assignment method adopts a high response ratio priority scheduling strategy to determine the priority of jobs in the buffer,which is used to control the assignment process of the jobs in the buffer,further reduce the probability of occurrence of deadlock phenomenon,and combine with the global optimization method to obtain optimization results.The effectiveness and feasibility of the proposed scheme in solving the scheduling problem of LBRHFSP are proved by the example simulation.