Research On Bi-objective Algorithm Of Scheduling Considering Rejection On Parallel Batch Machines With Different Capacities

Production scheduling plays an important role in daily production activities.As a typical combinatorial optimization problem,production scheduling problem has a wide application background,such as port cargo handling,logistics transportation and communication fields.The significance of studying the production scheduling problem is to maximize the profit,improve the utilization rate of resources and the competitiveness of enterprises by reasonably allocating limited resources.With the development of society and the progress of science and technology,the production scheduling problem is becoming more and more complex,the classical scheduling problem has been unable to meet the needs of rapid development,people have shifted their attention and research focus to the scheduling problem on batch processing machines,which is generally referred to as batch scheduling problem.Batch scheduling problem is developed from the classical scheduling problem.The main difference between them is that one machine can process multiple jobs at the same time,and the jobs are processed on the machine in the form of batch in the batch scheduling problem.The background of batch scheduling problem is more complex than that of classical scheduling problem,which involves more constraints and tends to the real production situation.The complexity of batch scheduling problem makes it more difficult.Many batch scheduling problems with one single machine are NP hard,so researchers are still looking for more efficient and convenient methods to solve the problem.Firstly,this thesis briefly introduces the research background and significance of production scheduling problem,and then uses the classic three-field notation to describe the scheduling problem.This thesis also introduces the main characteristics and research status of batch scheduling problem,and gives a brief overview of the research results of batch scheduling from five aspects:single machine,multiple machines,non-identical machine capacities,rejection cost and the number of objectives.Secondly,several algorithms for batch scheduling are in troduced briefly.These algorithms are divided into three categories:deterministic algorithm,heuristic algorithm and meta-heuristic algorithm.Then,the characteristics,framework and several representative algorithms of this three kinds of algorithms are introduced in detail.Thirdly,the parallel batch scheduling problem with non-identical machine capacities of minimizing the makespan and the total rejection cost simultaneously is discussed.Firstly,the problem is described,and then a Pareto-based ant colony optimization(FPACO)algorithm is proposed to solve the problem.A first job selection algorithm based on weak-restriction is presented,two candidate lists are designed according to the characteristics of the problem to improve the searching efficiency of ant colony,and the heuristic information and pheromone are designed to guide the searching behavior of ant colony.In order to improve the quality of solution,a local optimization algorithm based on exchange is provided.Finally,the FPACO algorithm is described in detail.Fourthly,the comparison algorithm is briefly introduced,the experiment and parameter setting are determined,the performance of all algorithms is verified by simulation experiment,and the algorithm performance is measured and analyzed by four evaluation metrics such as coverage rate and solution space.It can be seen from the experimental results that the performance of the presented algorithm FPACO is significantly better than the other four comparison algorithms.To compare the solution quality of the five algorithms clearly,the solution distributions of the algorithms on some instances are also drawn.In the last part,the bi-objective batch scheduling problem considering rejection based on the weak-restriction and the proposed algorithm are summarized,the further research direction is pointed out finally.