Application Of K-means Clustering Algorithm In Distributed Permutation Flow Shop Scheduling Problem

Under the general trend of economic globalization,distributed scheduling has attracted the attention of many enterprises,and has become one of the important research directions for enterprises to improve economic benefits.The purpose of this paper is to design an algorithm to solve the problem of job allocation and job sequencing for the distributed replacement flow shop scheduling problem,so as to inspire the actual production of the distributed workshop.Firstly,this paper constructs a distributed displacement flow shop scheduling model,and proposes a NEH-k heuristic algorithm based on the combination of K-means clustering and NEH algorithm.The processing time of workpieces on the machine is clustered as the clustering standard,and then the obtained cluster sets are evenly distributed to each factory in turn,averaging the total processing time of each factory as much as possible.This paper also improves the fitness function and cross mutation operator of genetic algorithm by using the idea of K-means algorithm,so that the improved genetic algorithm can retain the diversity of population and break away from local optimization in the calculation process.Compared with the existing heuristic algorithms and intelligent algorithms,the performance of NEH-k algorithm and genetic k-means algorithm is evaluated.The results show that the two algorithms have good robustness and accuracy.