Research On Multi-Machine Scheduling Algorithm Based On Ant System

Production scheduling problem is a kind of combinatorial optimization problem with wide application background.It exists in many fields in real life,such as semiconductor chip manufacturing,steel manufacturing and automobile freight transportation.The main purpose of research on production scheduling problem is because it plays an extremely important role in improving labor productivity and resource utilization and reducing the production cost of enterprises,and its research results have been very rich.Batch processing machine scheduling problem is an important branch of the production scheduling problem.It is an important extension of the classical scheduling problem,which is a new type of scheduling problem originated in the semiconductor manufacturing process.Batch processing machine scheduling problem unlike the classical scheduling problem,the obvious feature is that a machine can process multiple jobs simultaneously.Due to this type of scheduling problem needs to assign jobs to machines,and also includes the strategy of grouping the jobs into batches,it is much more complicated than the classical scheduling problem.Many batch scheduling problems known or even single machine environment are proved NP-hard.This paper first introduces the research background of production scheduling problem,and then summaries the current research status of batch scheduling problems from the single machine environment,the parallel machines environment,the flow shop machines environment and the job have different arrival times.Then we introduce two mainstream algorithms which are used to solve these batch scheduling problems,including deterministic algorithm and approximate algorithm,and then briefly summarize the characteristics of these two algorithms and introduce these representative algorithms of these two mainstream algorithms.Then,the paper discusses the batch scheduling problem of minimize the total weighted completion time for different size jobs under the same capacity parallel batch processing machines environment.First of all,we make assumptions about the problem and establish the mathematical model of the problem.In order to measure the performance of the algorithm,an effective lower bound of the problem is given.Then,we propose a heuristic algorithm and a meta-heuristic algorithm based on ACO to solve the problem,respectively.In the meta-heuristic algorithm based on ACO,the candidate list is constructed according to the remaining capacity of the batch,so as to reduce the search space of the ant and propose heuristic information based on the candidate list to guide the search behavior of the ant to further improve the quality of the solution.Then the performance of the proposed algorithm and other existing algorithms are compared by simulation experiments.The experimental results show that the proposed ACO algorithm is superior to other algorithms.In addition,the paper also gives the experimental results of these algorithms compared with CPLEX in the case of small-scale jobs.Finally,the parallel batch processing machines scheduling problem with minimize the total weighted completion time of the job with the different sizes and the proposed solution algorithm are briefly summarized,and made a prospect of the further research direction in the future.