Hyper-heuristic With Dynamic Decision Blocks And Its Application In Scheduling Problems

Scheduling problem is to conduct the plan of the production schedule.For manufacturing,it is mainly about the assignment of different sub-tasks of work,which are processing sequence and the order of processing,for the purpose of achieving the minimizing of makespan or the shortest of total weighted tardiness under some constrains.The production scheduling problem is discussed based on the analysis of the related research results at home and abroad and combines with the actual production situation of manufacturing enterprises.Firstly,the job shop problem and the inter-cell scheduling with limited transportation capacity are described and mathematically formulated given the constraints in practice.In this paper,the job shop problem and the inter-cell scheduling with limited transportation capacity are analyzed.A dynamic non-sequential decision block-based hyper heuristic is proposed,which can solve the scheduling problem.On the basis of the dynamic non-sequential decision block-based hyper heuristic,grouping genetic algorithm is adopted which makes decisions be adaptive to any combination,and appropriate heuristic rules are selected for each decision block.And then comparisons between the proposed method and hyper heuristics with different decision block strategies are conducted.The computational result indicates a better performance of the proposed method in minimizing makespan and computational costs.Compared with the existing research,the main contribution of this paper are the following three points:(1)the dynamic decision block strategy can reduce the search space,so that it can effectively improve the computation efficiency of the hyper heuristic algorithm;(2)dynamic and discontinuous decision block partitioning strategy could make up for the drawback of continuous division block which may fall into local optimal solution;(3)the grouping genetic algorithm is a kind of new clustering algorithm,and the improvement of group coding method is suitable for the decision-making of block any combination.Based on algorithms building the population initialization scheme and the improved genetic operators,genetic algorithm balances efficient computational efficiency with the ability of finding optimization.