Analysis And Algorithm Research Of Parallel Machines Batch Scheduling Problem Based On Incompatible Job Families

Scheduling has always played a crucial role in the production management of enterprises.The aim of scheduling is to allocate and arrange the limited resources reasonably,and optimize one or more objectives.A reasonable scheduling plan can improve the production efficiency and enhance the viability and competitiveness of enterprises.With the rapid development of manufacturing,production methods have changed and production scale has become larger.Some new scheduling problems have gradually emerged,one of which is called batch scheduling problems or batch processing machines scheduling problems.It is noted that a machine can process several jobs simultaneously in batch scheduling problems which is different from the classical scheduling problems that a machine can only process one job simultaneously.In fact,the batch scheduling problems can be divided into two sub-problems,machine assignment problem and batch forming problem.The batch scheduling is more efficient for allocating and using resources and becomes an important branch in scheduling problems.The batch scheduling problems are very common in actual production,especially in the semiconductor industry.In order to minimize the makespan,this paper has studied a parallel batch machines scheduling problem with incompatible job families,which has two constraints,including non-identical job size and arbitrary release time.After analyzing the actual problem,the problem is reasonably simplified and the relevant assumptions are introduced.A mixed integer programming model is established based on several variables and inequalities.According to the characteristics of the scheduling problem and the objective function,RO,PO and SO heuristics are proposed respectively from three angles,and the three heuristics give their own solutions for the problem through the same example.In addition,a lower bound is proposed as the standard solution for testing the efficiency of heuristics,and the correctness of this lower bound is proved.What's more,the improved artificial immune system algorithm(AIS)and discrete particle swarm optimization algorithm(DPSO)are proposed in this paper.In addition to the optimization of the algorithms structure,a better method for batch forming is combined with algorithms structure considering the characteristic of the problem,and the two algorithms can effectively solve the problem in this paper.Finally,the performance evaluation and analysis of the proposed heuristics and algorithms are carried out by the C++ language simulation experiment through the 450 problems generated randomly.The experimental conclusions of the data analysis are as follows: three heuristics can get good results in a short time,while the RO heuristic and PO heuristic perform better.However,the performance of three heuristics are all getting worse when the problem scale is getting larger.The improved artificial immune system algorithm and the improved discrete particle swarm optimization algorithm are stable,but the performance of the improved artificial immune system algorithm is better than the improved discrete particle swarm optimization algorithm.Otherwise,the solution obtained by RO heuristic can be applied to the improved artificial immune system algorithm as an initial solution to effectively improve the performance of the algorithm.