Research On Scheduling Algorithm For Minimizing Total Completion Time On Parallel Batch Machines With Arbitrary Capacities

The production scheduling problem is a type of complex combinatorial optimization problems existing in many real fields,such as the foundry industry,metal processing industry,logistics industry,and communication industry.The main purpose of production scheduling is to allocate resources during processing reasonably to improve resource utilization and productivity.With the advancement of times and the update of technologies,the problem of production scheduling has become more and more complicated.And research on production scheduling has gradually extended from classical scheduling problems to batch scheduling problems.The batch scheduling problem is an extension of the classical scheduling problem.The complexity of the BSP lies in the fact that the batch processing machine can process multiple jobs at the same time.Although batching and scheduling of the jobs need to be considered simultaneously to solve the batch scheduling problem,the efficiency of the production systems can be greatly improved.This thesis first briefly introduces the related research background of production scheduling problems and the production scheduling problems classified according to machine environments.Then the algorithms commonly used to address the batch scheduling problems are briefly introduced,including deterministic algorithms,heuristic algorithms and meta-heuristic algorithms.Next,this thesis studies the problem of scheduling a set of jobs with arbitrary sizes on parallel batch machines with different capacities.The objective is to minimize the total weighted completion time of jobs.After the studied problem is described,a mixed integer programming model is provided.Then,an algorithm of computing the lower bound is proposed to evaluate the effectiveness and performance of the algorithms.Besides a heuristic algorithm,two improved algorithms based on ant system and max-min ant system are respectively presented to solve the studied problem.A new strategy of first job selection based on job weights is designed and used to construct the solutions.At the same time,in order to reduce the complexity of constructing solutions and narrow the search scopes of ants,a novel candidate list is constructed according to the remaining capacity of the current batch.Moreover,in order to direct the ants effectively,a heuristic information based on the constructed candidate list is designed.Additionally,for each constructed solution,a local search strategy is applied to further improved the quality of the solution,through the strategy of neighborhood searchThe two proposed ACO-based algorithms in this thesis are compared with the existing two other meta-heuristic algorithms,i.e.,RKGA and PSO,through extensive simulated experiments.Moreover,experiments are respectively performed on instances with two different machine capacities and three different machine capacities to compare the results of the algorithms with different settings of machine capacities.In the case of machines with three different capacities,simulated experiments are executed with different combinations of the numbers of machines with different capacities.And,the effect of the distribution of machine capacities on performance of the algorithm is analyzed.Furthermore,the effectiveness of the new strategies adopted in the proposed algorithms is tested and verified through simulated experiments.Finally,the research work of this paper is summarized,and the work to be studied in the future are expected.