An Intercell Scheduling Approach Based On Genetic Programming And Genetic Algorithm

Cellular manufacturing, in which the parts or part families requiring similar production processes are grouped into distinct manufacturing cells, is one of the most effective ways for production. It has been widely adopted by many companies in Japan, Europe and the United States. In practical application, some exceptional parts have to be processed in different cells. In order to schedule these exceptional parts, collaboration among different cells is needed for integrated production processing path decision. In this case, inter-cell scheduling problem arises.Our survey of the equipment manufacturing industry of China indicates that, for some complicated assemblies, such as synthetic transmission devices, intercell transfers occur in the processing routes of more than 50% of parts, and out of the tardy parts, more than 75% are caused by inefficient intercell cooperation. Therefore, there is a need to study scheduling in the context of multiple cells with intercell transfers.The related work is studied and analyzed first. Based on the actual conditions of equipment manufacturing production, the issue of inter-cell scheduling considering transportation capacity is studied. Aiming at this problem, a corresponding inter-cell scheduling approach is proposed in this paper.Firstly, a detail description of the intercell scheduling problem considering transportation capacity is given and a mathematical model is formulated.Secondly, based on the previous model, a hyper-heuristic approach based on genetic programming and genetic algorithm(HHGPA) is proposed. In the first stage, genetic programming(GP) is used to generate new heuristic rules automatically based on the information of the machines or vehicles, to increase the diversity and effectiveness of the candidate rules. In the second stage, a rule selection genetic algorithm(GA) is developed to select appropriate rules from the obtained rule set, for the machines and vehicles. Finally, the scheduling solutions are generated according to the selected rules. A comparative evaluation is conducted, with some state-of-the-art hyper-heuristic approaches, with a meta-heuristic approach that is suitable for large scale scheduling problems, and with adaptations of some well-known heuristic rules. Computational results show that the HHGPA approach has advantages over other approaches in solution quality, and is especially suitable for problems with large instance sizes.Finally, to solve the problem of premature convergence and inferior local search ability, a catastrophe operator and a local search algorithm based on hill climbing are proposed and added to HHGPA. Experimental results show that the modified HHGPA has a significant improvement. Compared with the CPLEX, the proposed algorithm has a significant improvement on performance and computational efficiency.The contribution of this paper includes:(i) a mathematical model for the intercell scheduling problem considering transportation capacity;(ii) an efficient hyper-heuristic approach based on genetic programming and genetic algorithm is developed;(iii) an improved HHGPA with a catastrophe operator and a local search algorithm based on hill climbing is proposed.