Applications And Research On History-Guided Multi-Objective Batch Scheduling Evolutionary Algorithm

As one of the vital research issues in operations research,production scheduling has many application scenarios and has attracted the attention of experts and scholars for a long time.With the industrial development and technological progress in recent years,the industrial production environment has gradually become diversified,complicated and intelligent.In order to minimize production costs and maximize product profits in such a production environment,the reasonable allocation of limited resources such as manpower,machinery,raw materials,energy,and time is particularly critical for decision makers.This is also the main optimization purpose of production scheduling.In short,how to optimize the production process through production scheduling has become one of the issues that the decision makers of modern enterprise cannot ignore.Batch scheduling is an important branch of production scheduling and exists in manufacturing systems of most industries,such as casting industry,furniture manufacturing,metal manufacturing,aeronautical manufacturing,pharmaceutical industry and logistics freight.In batch scheduling problem,several jobs are grouped into one batch and processed simultaneously.The longest processing time of all jobs in a batch is regard as the processing time of the batch.The processing of each job must be completed without interruption.Because the real production environment is always complicated,decision makers are more inclined to take into account many objectives at the same time.Therefore,this thesis proposes an optimization algorithm to solve the multi-objective batch scheduling problem that is closer to the real production environment.Firstly,this thesis briefly introduces the research background and significance of the batch scheduling problem,and analyzes the research states of the batch scheduling problem from the perspectives of the production environment and optimization objectives.Secondly,this thesis introduces the existing related work of the batch scheduling problems and multi-objective optimization algorithms.Thirdly,this thesis introduces a multi-objective batch scheduling problem with different job sizes,processing times,due dates to minimize three objectives,at the same time,i.e.,the minimization of the makespan,the total weighted earliness/tardiness penalty and the total energy consumption.Fourthly,this thesis presents a history-guided evolutionary algorithm based on decomposition with local competition named HGEA/D-L to solve the studied problem.There are two novel strategies adopted in HGEA/D-L.Firstly,a local competition strategy based on two structural indicators can effectively ensure population quality and convergence.Secondly,the decomposition-based internal replacement strategy updates the historical information matrixes by extracting the structural characteristics of elitist individuals and guides the generation of new individuals through it.In addition,This thesis gives the time complexity analysis of the proposed algorithm.Fifthly,this thesis selects four comparative algorithms,and designs two groups of compared experiments to comprehensively evaluate the performance of the proposed algorithm.The experimental results show that the proposed algorithm is superior to the comparative algorithms.And the significance test shows that the result of proposed algorithm is significantly different from those of the comparative algorithms.Finally,this thesis summarizes the studied multi-objective batch scheduling problem and the proposed history-guided multi-objective evolutionary algorithm based on decomposition,and provides the directions of future research.