Research On Coevolutionary Algorithm For Multi-objective Non-identical Parallel Batch Scheduling Problem

The advancement of science and technology and the increase in production requirements have caused manufacturing enterprises to face increasing production pressure,which has led to high demands for new scheduling schemes.The batch scheduling is much closer to the real production environment,and is an extension of the traditional scheduling.Compared with the traditional scheduling problem,the batch scheduling model can improve production efficiency and resource utilization.Therefore,the research on batch scheduling can provide support for enterprises to improve productivity,enhance the core competitiveness,and decision making on production plans.In a manufacturing factory,aperiodic machine update causes that new and old machines with different processing capabilities coexist in the shop.In this case,it is very challenging to improve productivity and reduce resource consumption at the same time.For the last hightemperature test stage of chips in the semiconductor manufacturing industry,the chips and hightemperature ovens are regarded as jobs and batch processors,respectively.As a result,the problem is abstracted as scheduling a set of jobs with arbitrary arrival times,different sizes and unequal processing time on a set of non-identical parallel batch processing machines to minimize makespan and total machine energy consumption,simultaneously.The main work of this thesis is as follows:(1)The problem studied in this thesis is described in detail firstly.And,a mixed integer programming model is established.Then,a dual ant colony co-evolution algorithm based on the characteristics of the problem is proposed to solve the studied problem.In the proposed algorithm,heuristic information based on problem features is used to construct the solution.The independent search of the two ant sub-colonies is able to improve the diversity of the algorithm,as well as the convergence of the algorithm.Finally,simulated experiments are conducted to verify the effectiveness of the proposed algorithm.(2)In the proposed dual ant colony coevolution algorithm,since the two ant sub-colonies are designed to search toward different directions,it is found that the area between the two directions is unable to search effectively by the two ant sub-colonies.Therefore,an improved algorithm with two novel strategies called multi-population bi-objective co-evolutionary algorithm is further presented to solve the studied problem.Firstly,a strategy based on the maximum angle is put forward to define the preference vectors.Secondly,the ants are selected according to their population contribution to update pheromone trails.Compared with the dual ant colony co-evolution algorithm,a new ant sub-colony in the multi-population bi-objective co-evolution algorithm is designed to balance the search between the two sub-populations searching in the directions oriented to different objectives independently to avoid losing effective solutions in the common search area.Hence,the diversity and convergence of the algorithm are improved with ensuring the found solutions distributed more uniformly.Finally,through a large number of simulated experiments,the effectiveness and efficiency of the multipopulation bi-objective co-evolutionary algorithm are verified.