Hyper Heuristic Based Approach For Intercell Scheduling Problem Considering Multiple Machine Type

The typical production mode of the equipment manufacturing industry of China can be described as "high variety and low volume in mixed production lines", which makes the Cellular Manufacturing System is difficult to achieve. Moreover, as the processing route of parts becomes more complicated, it is necessary to coordinate the scheduling of single processing machine as well as batch processing machine. Based on researches of some related work, the complexity of intercell scheduling problem considering single processing machine and batch processing machine is analyzed.Firstly, the intercell scheduling problem considering single processing machine and batch processing machine is described in detail, then the assumptions, constrains, and variables are designed, during which the problem model of the addressed problem is proposed.Secondly, an Ant Colony Optimization Based Heuristic Search Approach is proposed. In this method, a ACO approach is designed to search and select heuristic rules, and the solution of the problem could be constructed by the selected rules. The problem is divided into three sub-problems, ie. part assignment sub-problem, part sequencing sub-problem, and batch formation sub-problem. The ACO approach develops different pheromone structures for each sub-problem, respectively, and updates the pheromone trails integratedly to achieve a cooperative optimization. As compared to genetic algorithm that is widely used in hyper-heuristics, the proposed approach has better performance with respect to the problem addressed in this paper.Thirdly, basing on the above approach, an approach which combines heuristic generation and heuristic selection is adopted. In the heuristic generation stage, Genetic Programming is adopted to generate new heuristic rules, and an abandon strategy is adopted for the new candidate heuristic rules. In the heuristic selection stage, a failure perception strategy is used to avoid local optimum.Finally, a series of experiment is designed to verify the the performance of the addressed algorithms. The Genetic Programming and the abandon strategy have good performance on obtaining good candidate heuristic rules. The modified ACO approach shows well searching performance as the failure perception strategy can easily avoid local optimum.