| Scheduling is one of the most common combinatorial optimization problems in real life. High quality scheduling scheme will help reduce production costs, increase resource utilization, improve productivity. Batch scheduling is a branch of Scheduling problem. Compared with classical scheduling problem, batch scheduling break assumption of classical scheduling problem. In batch scheduling, a machine can process multiple job simultaneously. Problem of batch scheduling are encountered in many practical environments. For example, handling of cargo in port areas, burn in operation in ceramic processing, freight transportation. Therefore, from practical point of view, study of scheduling batch machine with non-identical job sizes can give more effective guidance to real production.First, related concepts of combinatorial and computational complexity problem are introduced, then describe three-parameter representation and the classification of scheduling problem. Distinguish between the classical scheduling problem and batch scheduling, batch scheduling and batch scheduling with non-identical size.Secondly, paper review previous related studies, the solution of such problems existing three main methods: Mathematical Programming, Heuristic Rule, Heuristic Algorithm. Principles and basic steps of these various methods are introduced.Thirdly, an Adaptive Ant Colony Simulated Annealing Algorithm is presented. The algorithm adopts Simulated Annealing policy to implement a new mixed strategy to update pheromone and an adaptive state transition probability is also presented.This adaptive state transition probability can effectively avoid search stagnation of the algorithm. The experimental results show that AACSA has better performance than BACO(Batch Ant Colony Optimization Algorithm), SA(Simulated Annealing) and the heuristic BFLPT.Finally, summarize the content and result of our paper, then give some further suggestions and future research prospects. |
PDF Full Text Request