Research On Workshop Scheduling Problems Based On Biological Computing Models

In the era of global economic integration,manufacturing industry occupies a pivotal position in the global economic share.Efficient production can improve enterprise profits,market share,and enable enterprises to seize the opportunity in the new product release,and efficient production of enterprises can not be separated from the optimization of all kinds of scheduling problems on the product line.Common shop scheduling problems in production include job shop scheduling problem(JSSP),hybrid flow-shop scheduling problem(HFSP)and flexible job shop scheduling problem(FJSP).Because different scheduling problems correspond to completely different production backgrounds,technological processes and constraints,the model or algorithm for one scheduling problem is not universal in other scheduling problems.No matter using accurate method or approximate method,how to design an efficient solution model or algorithm to improve the solution accuracy and reduce the time consumption is a challenge to solve all kinds of shop scheduling problems,and is also the focus of common concern of industry and academia.Biological computing refers to a new computing model abstracted from the inherent information processing mechanism of microscopic biological systems.It has the advantages of distributed and large-scale parallel computing.Among them,DNA computing,with its advantages of large-scale parallelism and high density storage,makes exhaustive search possible and can solve combinatorial optimization problems in linear time.As a representative of the most advanced DNA computing model,probe machine(PM)has shown great computing power and application prospect in solving graph theory related problems with its nonlinear access and completely parallel processing mode.In addition,in the aspect of membrane computing,the spiking neural P(SN P)system has become the research hotspot of membrane computing models in recent years because of its simple operation mode and flexible digraph topology.How to make use of the advantages of distributed parallel computing of membrane system,improve and optimize the existing intelligent algorithm reasonably,and apply it to practical problems,has important research value and prospect for the extension of membrane computing theory and application.The main research contents of this thesis are summarized as follows:(1)Length measurement function based on DNA manipulation and JSSP-oriented EALDNA algorithm are proposedIn this thesis,a length measurement function based on DNA manipulation is designed,and an EALDNA algorithm is proposed to solve JSSP by combining with other existing DNA manipulation operators.This part is divided into the following three parts:(1)Inspired by operation-based coding,this thesis first proposes a new DNA strand coding strategy,which is not only beneficial to the operation and implementation of DNA coding,but also can eliminate the possible redundancy caused by operation-based coding,and ensure that any coding sequence is a feasible solution to the problem.(2)The proposed EALDNA algorithm is composed of four subalgorithms,which makes full use of and embodies the advantages of large scale and parallelism of DNA computing.The operational complexity of the algorithm is proved to be in linear time.(3)Considering the above characteristics of the EALDNA algorithm,we use the Docplex library in Python that supports multi-core and multi-thread parallel optimization for simulation modeling.In this thesis,a wide range of experiments are carried out on different scale JSSP instances,and the results show that the proposed algorithm is superior to the comparison algorithms.(2)Construct MPOIPM model and MPOIPM-CP modeling method for HFSPAn improved probe machine model(MPOIPM)is constructed for HFSP,and a constraint programming modeling method(MPOIPM-CP)is proposed based on two data liraries in MPOIPM.Probe machine(PM),as the most advanced DNA computing model,has nonlinear access and complete parallel processing mode.However,PM only supports single-stage probe operation,which not only cannot handle some complex graph theory problems,but also restricts the computing power of PM.This part is divided into the following two aspects:(1)In this thesis,an improved probe machine model(MPOIPM)with multi-level probe operation is proposed.Then,HFSP is transformed into a graph theory problem by means of disjunctive graph model,and data library and probe library are designed to solve this problem.Finally,the operational complexity analysis of MPOIPM model is given.(2)Based on the two data liraries constructed in MPOIPM,this thesis also constructs two triplet sets specially for constraint programming modeling.There is a one-to-one mapping relationship between the data liraries and the tuple sets.On the basis of the above two tuple sets,this thesis conducts constraint programming modeling for HFSP.Then,the optimal search strategy combination was determined by Taguchi experiment design,and the scale complexity and computational complexity of the model were analyzed.The results show that MPOIPM-CP proposed in this thesis is superior to the comparison algorithms in both solving time and solving precision.(3)Construct SNPE model and SNPE-IAHGA algorithm for FJSPEnzyme spiking neural P(SNPE)system was proposed for the first time,and the SNPEIAHGA algorithm for FJSP is designed based on this system.This part is divided into the following three aspects:(1)The SNPE model is constructed and its formal definition is given.Compared with standard SN P and its variants,SNPE is not only improved in object,rules and system operation mode,but also more in line with the biological reality of nervous system.In the neurons of the SNPE system,the number of spikes and enzymes together constitute the consumption condition of rule execution,determining not only which rule will be executed,whether it will be executed continuously,but even the number of times the rule can be executed in parallel.This not only enriches the existing theoretical model of SN P,but also makes the operation of the system more flexible.(2)In this thesis,the computing power of SNPE in generation mode,acceptance mode and small general computing devices is verified respectively.In particular,SNPE can use fewer neurons and rules than other SNP variants when simulating small general computing devices.In terms of computational case analysis,a SNPE model is also constructed which can solve subset sum problem consistently,and is superior to all comparison models in terms of the number of computational steps required.As the controller of whether the rules can be consistently executed,enzymes are more flexible and prominent in solving NP-complete problems such as subset sum problem.(3)Finally,a probability-weighted SNPE model is designed to implement the IAHGA algorithm.Adaptive hybrid genetic algorithm based on SNPE(SNPE-IAHGA)is mainly composed of two sub-algorithms: improved adaptive genetic algorithm and two-level neighborhood search algorithm.The former is to integrate the number of iterations with the evaluation of individual merits and demerits,and put forward an improved adaptive crossover and mutation probability calculation formula.The latter move across machines and within machines based on non-overlapping key operations and reverse key blocks respectively.(4)Practical production scheduling application based on MPOIPM-CP and SNPE-IAHGAThe application research of this part is mainly divided into the following three parts:(1)The proposed MPOIPM-CP is applied to two actual production scheduling cases of a water meter manufacturer.The two cases are divided into small scale and large scale,both of which belong to HFS-UPM problems.The comparison in large-scale case II shows that MPOIPM-CP can increase the manufacturing efficiency of this enterprise by 3.13%.(2)The proposed MPOIPM-CP is applied to the automobile engine cylinder block production line.This case belongs to HFS-IPM problem.The results show that MPOIPM-CP increases the manufacturing efficiency by 4.5%.(3)The proposed SNPE-IAHGA is applied to a mold manufacturing workshop.This case is a green PFJSP problem aiming at minimizing total energy cost and completion time.Under the premise that there is no essential difference in computing time,the proposed algorithm gives better scheduling solutions than the comparison algorithms in terms of completion time and total energy cost.To sum up,biological computing opens up a new channel and provides a new idea for solving combinatorial optimization problems,especially several kinds of shop scheduling problems,with its advantages of large-scale,distributed and parallel computing.According to the existing literature,it is a promising research direction of biological computing in the field of shop scheduling to use the distributed parallel framework of membrane computing to optimize the improved intelligent algorithm,and transform the shop scheduling problem into a graph theory problem and design appropriate DNA computing models and algorithms to solve it.