Research On Batch Processing Machine Based On Ant Colony Optimization

Batch processing machine (BPM) is one of very important model production scheduling problems. Theoretically, it is a breakthrough and an extension of classic scheduling theory. The BPM problem ignores the restriction on the number of jobs that can be processed on a machine simultaneously, which shows a new research direction in production scheduling. BPM, extracted from the last phrase of semi-conductor production, is a new kind of scheduling problem and has a very strong background in application. Meanwhile, BPM is NP-hard which shows that it is very important to design a simple and effective algorithm for solving the problem.Ant colony optimization (ACO) proposed recently is an effective meta-heuristic algorithm in solving combinatorial optimization problems. It is a constructive based meta-heuristic, which means a complete solution was constructed by adding solution part into it. Therefore, the ACO algorithm is suitable to solve BPM because of its characteristic in batching. In addition, the ACO algorithm is population-based meta-heuristic which has memory storage capacity. The combination of these characteristics makes the ACO algorithm as a very unique meta-heuristic for solving the BPM problem. However, ACO has some shortcomings in long run time and easily trapped in local optimal in practice. Therefore, base on the structure analysis of the BPM problem, several improving scheme was proposed to promote the quality and efficiency of ACO in solving BPM.The research focuses on the development of efficient algorithms for solving BPM problem. Ant system algorithms for solving different types of BPM problems were proposed. Specifically, the main research and innovations include:1. The application of algorithm ant system (AS) was studied in the single batch processing machine with non-identical job sizes. First, the mathematic model of the problem was proposed. Lower bounds and heuristics of the problem already existed were also presented. Two ant system algorithms based on job sequence and batch sequence separately were given according to different coding schemes. The objective of the mathematic model was to minimize makespan. The conception of batch weight was introduced as the heuristic information of the ant system algorithm considering this characteristic. At the same time, traditional ant system algorithms have many shortcomings like slow convergence and easily trapped in local optimization. Several improving ways including setting different initial pheromone and adopting local optimization were used to overcome these shortcomings. Experiments were performed to verify the effectiveness of the algorithm. The result showed that the AS based on batch sequence was much better.2. The application of algorithm max-min ant system (MMAS) was studied in the single batch scheduling problem with dynamic job arrivals. First, the mixed-integer programming model was established. Each job has different arrival time in the problem. Considering this characteristic, two different candidate lists was proposed according to whether the current batch was delayed in the phrase of constructing feasible solutions. Heuristic information of each candidate list was designed separately due to the different influences of the different candidate list to the solution construction. The standard ant system algorithm was compared with MMAS considering candidate list in the experiment and the effectiveness of the later one was verified.3. The application of algorithm ant colony system (ACS) was studied in the single batch scheduling problem with non-identical job sizes and dynamic job arrivals. First, the mixed-integer programming model of the problem was established and the model was solved in CPLEX. The conception of idle space was proposed by analyzing the effect of job arrival time and job size on the optimization objective. In addition, to minimize idle time of the batch list was equivalent to minimize the makespan of the problem. The ACS algorithm with dynamic heuristic information was designed to guide the ant behavior more accurately. The solution space was optimized and the convergence speed was improved by using candidate list strategy. Experiment was performed to verify the effectiveness of the algorithm by comparing with CPLEX, GA and the lower bound of the algorithm. The results showed that the proposed algorithm could find feasible solution with reasonable time consuming.4. The multiple objective ant colony optimization (MOACO) algorithm was studied in the parallel batch scheduling problem. First, the mathematic model of the multi-objective batch scheduling problem was given. The idle space and tardy space were defined according to two different optimization objective, minimize makespan and minimize the maximum tardiness, based on which. the heuristic information and candidate list of the MOACO algorithm was designed. During solution construction, a new solution construction mechanism was proposed by using the MOACO's characteristics in construction. The mechanism reduced the three construction steps, that are batching jobs, ordering batch list and scheduling batches to machines, into one step, which obviously improved the efficiency in optimization. The experiment was performed to evaluate the algorithm in Pareto solution quality, solution variety and time consuming.In short, research on batch processing machine problems is of both theoretical and practical significance. As the problems discussed in this study are NP-hard, optimization methods for these are very important. In this study, a single objective optimization problem for a batch processing machine problem with non-identical job sizes and dynamic job arrivals was first addressed. The problem was then extended for multi-objective optimization problems in parallel machines environment, which is much more complex and practical than the previous one. For different batch scheduling problems, the mathematical model was first constructed, and a valid lower bound was next proposed. An effective ant colony optimization approach was then designed for solving these problems. Aiming at the drawbacks that traditional ACO algorithms are time-consuming and easy to get trapped in local minima, several strategies were proposed to improve the effectiveness and efficiency of ACO algorithms based on the analysis of the structure of batch scheduling problems, such as designing good pheromone trails and heuristic information, constructing candidate list based on constraints and objectives, improving the updating method of pheromone trails, and introducing local search technique. It is clear that the contents in this study are interrelated and gradually progressive. This study provides some novel theory and methods for batch scheduling problems, and expands the theoretical and practical research of ACO algorithms.