Research On Distributed Shop Scheduling Methods Based On Memetic Algorithm

Distributed manufacturing is the inevitable trend of manufacturing industry development.It has the advantages of low cost,low risk and high efficiency brought by rational utilization of resources.In general,traditional workshop is related with single workshop which could not meet current manufacturing needs,while distributed production considers the collaborative production between multiple workshops.Thus,Distributed Scheduling Problem is more complex and solving this kind of problem is of great difficulty which has important academic significance and application value.This thesis is aimed at Distributed Permutation Flow Shop Scheduling Problem(DPFSP),Energy-efficient Distributed Permutation Flow Shop Scheduling Problem(EEDPFSP),Distributed Job Shop Scheduling Problem(DJSP),Energy-efficient Distributed Flexible Job Shop Scheduling Problem(EEDFJSP).Combined with the characteristics of different types of distributed scheduling problems,related hybrid integer models are established,and related optimization algorithms based on Memetic Algorithm(MA)are proposed to solve the above four problems.The main research contents of this thesis are stated as follows:For distributed permutation flow shop scheduling problem,a mathematical model is established to minimize the maximum completion time(Makespan),and a hybrid optimization algorithm based on Memetic Algorithm is proposed to solve the problem.In the proposed algorithm,a two-layer coding mechanism is designed for the assignment of job between different workshops,permutation within workshop.And a initialization mode is proposed with the characteristics of the problem in order to obtain solutions with high quality.Moreover,evolutionary operation and local search algorithm based on critical workshop are proposed to improve the global search ability and local search ability.In order to evaluate the performance of MA,MA is compared with other algorithms with 180 test instances.Experimental results show that MA is superior to other algorithms in all instances.Aiming at the multi-objective distributed permutation flow shop scheduling problem,a mathematical model is developed to minimize the Makespan and total energy consumption,and a multi-objective Memetic Algorithm(MOMA)is proposed to solve the problem.In the algorithm,a hybrid initialization method is proposed based on the three-layer coding mechanism.And a local search strategy based on the optimization of the maximum completion time is designed to minimize the makespan and a local search strategy based on the waiting time is designed to minimize the total energy consumption.In order to test the convergence,spread and comprehensive performance of MOMA,MOMA is compared with other multi-objective algorithms.The experimental results show that the proposed MOMA has advantages in convergence and comprehensive performance of 40 instances.Aiming at solving distributed job shop scheduling problem,a mathematical model is formulated to minimize the Makespan.Compared with the distributed permutation flow shop scheduling problem,this kind of problem is more complex and needs to consider the sequence of different operations of different jobs.Therefore,a Knowledge-based Memetic Algorithm(KMA)is proposed based on problem characteristics.According to this problem with characteristics of distributed scheduling problem and job shop scheduling problem,the corresponding encoding mechanism,update operation and local search strategy based on critical workshops are designed in order to enhance the global and local search.In order to evaluate the performance of KMA in solving this problem,the proposed algorithm is compared with other algorithms with 240 distributed job shop scheduling problem instances.To solve the multi-objective distributed flexible job shop scheduling problem,a mathematical model is established to optimize makespan and total energy consumption simultaneously.This problem contains subproblems of the allocation of the different jobs in different workshops,operation sequence in each workshop and machine assignment of each operation.Based on the distributed job shop scheduling problem,a multi-objective Memetic algorithm(MOMA)is proposed to solve the multi-objective distributed flexible job shop scheduling problem.In this algorithm,a full decoding code,a hybrid initialization method of global selection,local selection and random selection are adopted in order to obtain the initial solutions.The population is classified by non-dominated sorting and the corresponding update operations are designed according to the different subpopulations,including five variable neighborhood search strategies.By comparing with other multi-objective evolutionary algorithms,the experimental results show that MOMA has obvious advantages in solving this kind of scheduling problem by comparing it with other multi-objective algorithms.According to the production situation of the left side outer plate processing workshop,the application of the proposed method is verified.The corresponding mixed integer programming model is established,and the theory and method in this paper are verified by an actual engineering case,which proves the effectiveness of the proposed algorithm.Finally,the above work and innovations of the thesis are summarized,and future research directions are discussed.