Research On The Solution Method Of Integrated Process Planning And Scheduling Based On Fitness Landscape Theory

Integrated planning process and scheduling (IPPS) problem is a typical schedulingproblem，which has proven an NP-Complete problem. The fitness landscape of such problemis very complex, so the traditional optimization algorithm can’t get the solution effectively,while most of the benchmark testing problems are far out of the optimal solutions. Therefore,the research on the solution method to IPPS problem still has a long way to run. The keypoints of the research lies in two aspects: one is to make efficient improvement to the processand operation of algorithm; the other one is to design an efficient hybrid optimizationalgorithm on the basis of the research on the fitness landscape of IPPS problem with thecombination of the existing optimization algorithm research.Combined with the existing research on IPPS problem, this paper presents an efficientsolution method to IPPS problem based on the improved genetic algorithm. With the analysisof basic genetic algorithm characteristics and the combination of the inherent characteristicsof IPPS problem, the improvement is made to the solution process of the algorithm whilereasonable design is also made to the basic elements of the algorithm, such as the algorithmencoding, update operator, etc. Experiments show that this method gets satisfactory results.Then taking a typical example as an object, this paper has an in-depth research on thefitness landscape problem of IPPS. It has a data analysis of the IPPS solution structure byintroducing the concept of Logistic Model. It is found out that the fitness landscape of IPPSproblem conforms to the distribution of Logistic Model, and at the same time, it proves thatthe Logistic Model of such problem possesses a distribution of high stability. Based on theLogistic Model distribution of IPPS problem, the neighborhood structure of local search isintensively studied and analyzed, which provides a better basis to design a highly qualifiedneighborhood structure in local search algorithm.With the above research, an efficient local optimization algorithm is designed based on thevariable neighborhood search (VNS), and it is embedded in the improved genetic algorithm toform a new efficient hybrid genetic variable neighborhood search (GAVNS) algorithm to theIPPS solution. This algorithm can well balance the global search ability and the local searchability, which makes up the disadvantage of one single algorithm, making the complex IPPSproblem solution more efficient. Those solutions to the24problems in the international Kim benchmark tests with this algorithm upgrades the world best solutions to nine problems. Andof the24problems,12problems have already got the optimal solutions. Experiments showthat this algorithm can solve IPPS problems effectively.Based on the above research, this paper designs and develops IPPS prototype system, andgives a brief introduction and presentation of this system.Finally, this paper has a summary and gives a further research orientation.