Research On Mixed No-wait Flexible Flow Shop Scheduling Problem

With the rapid development of the global industrial economy,the manufacturing industry needs to be transformed and upgraded in a timely manner,from high-speed development to high-quality development.In the shop scheduling problem,the situation where jobs are not allowed to have waiting time between some adjacent processes,while the rest of the processes have unlimited intermediate storage strategies and unlimited waiting time is called mixed no-wait.The research on mixed no-wait constraint can not only make the production meet the quality requirements of products,but also shorten the production process,thus improve the production efficiency of enterprises.Therefore,this thesis takes the mixed no-wait flexible flow shop(MNWFFS)as the research object,considers the production process and resource constraints,and establishes an integer programming model.In order to solve the NP-hard problems,an approximate algorithm based on artificial bee colony algorithm and genetic algorithm is proposed to obtain the near optimal solutions.Because the maximum completion time is one of the direct evaluation indicators to measure the production efficiency of enterprise,it is also the most widely used Indicator in flexible flow shop problem.Therefore,this thesis firstly takes minimizing the maximum completion time as the problem objective.Considering that in the actual production,the processing time of multiple parallel machines in the same stage is different due to their machine age and different degrees of wear,this thesis proposes a mixed no-wait flexible flow shop problem with unrelated parallel machines,and establishes an integer programming mathematical model by combining machine capacity constraints and process priority constraints.Based on particle swarm optimization algorithm,iterated greedy algorithm and variable neighborhood search algorithm,a hybrid discrete artificial bee colony algorithm is proposed.In this algorithm,the two-dimensional matrix is used for coding,the job right shift strategy is used for decoding,and the NEH heuristic algorithm is introduced to generate the initial population to improve the quality of the population.In the employed bee stage,with the help of the solution updating strategy in particle swarm optimization algorithm,single point column crossover and single point mutation operator are used to obtain the new solution.In the onlooker bee stage,a new solution with better quality is selected to perform the destruction and reconstruction operations in the iterated greedy algorithm,so as to improve the search ability of the algorithm.In the scout stage,the variable neighborhood search algorithm is introduced to generate a new solution to replace the historical worst solution.Finally,the proposed algorithm is compared with heuristic algorithm and existing algorithms.Simulation results show that the proposed algorithm can produce better solution in a reasonable time.With the diversification and personalization of customer needs,improving customer satisfaction has also become an important business goal of enterprise.In recent years,scholars have paid more and more attention to the total weighted time problem.This goal helps the manufacturing industry to improve the logistics balance of the different production lines,as well as to improve the time connection between stages,in relation to the logistics goals of work-in-process inventory and on-time delivery.Therefore,based on the above research,this thesis further studies the total weighted completion time problem in the flexible flow shop with the unrelated parallel machine environment.Considering the dynamic characteristics of the job and transportation time requirements between adjacent stages,an integer programming is established,and a iterated greedy genetic algorithm combining iterated greedy algorithm and genetic algorithm is proposed to obtain the near optimal solution of the problem.Combined with CDS heuristic rules and random program,the initial solution is generated,and the crossover operator based on process position and mutation operator based on job position are designed to obtain the solution of improved genetic algorithm.In order to avoid the genetic algorithm falling into local optimization prematurely,the previously generated population is divided into two subgroups according to the fitness value,and the destruction and reconstruction operations in the iterated greedy algorithm are applied to the worse subgroup.Then,three neighborhood local searches based on pairwise exchange,pairwise insertion and reordering of job position are proposed to obtain the neighborhood solution.Simulation experiments compare the proposed algorithm with several heuristic algorithms.Simulation test on different scale problems verify the effectiveness of the proposed algorithm.