Hybrid hyper heuristic approach design to flowshop group scheduling problems

In today's world, the changing structure of customer demand forces manufacturers to produce low-cost, high-quality products with increased product variety in a short period of time. In order for manufacturing companies to survive among their competitors, it has become crucial to optimize their production systems and to deliver a wide variety of products in a short time. However, high product variety leads to several challenges in the production process, such as increased setup times and transportation times—considered as waste—and a more complex operation scheduling process. To overcome these challenges, the Group Technology (GT) approach has been developed, whereby products (jobs) are grouped based on similarities in shape, material, production process, or other characteristics. Planning activities are then carried out based on these grouped jobs rather than treating each job individually. In this way, setup times between products are minimized, and the flow of materials and goods between processes is simplified. Planning activities in such systems are conducted on two levels. In the first level, the groups to be processed are determined. In the second level, the processing sequence of the jobs within each group is established. In this study, a method is proposed for a flow shop scheduling problem in which jobs are grouped, setup times are sequence dependent (vary depending on the previously processed group), and jobs do not wait between machines as (no-wait constraint). The addressed problem is of a non-polynomial time solvable nature with a large solution space. The research questions for this research is as follows: ● Do hyper heuristic methodology find efficient solutions to flow shop group scheduling problems? ● Is the Artificial Rabbit Optimisation Algorithm effective in solving flow shop group scheduling problems? ● Among the crossover and mutation operators applied to flow shop group scheduling problems in the literature, which have demonstrated effective performance? ● Do the modified crossover operators applied in this study enable an effective exploration of the solution space? ● How do the results of the developed method differ from those of the methods in the literature? Based on the conducted literature review, this study is the first attempt to apply the Artificial Rabbit Optimization Algorithm and develop a memetic algorithm based hyper heuristic method for the no wait flow shop sequence dependent group scheduling problem. The artificial babbit optimization algorithm, inspired by the behavior of rabbits in nature, is a relatively new algorithm that has the advantage of requiring only iteration number and population size as parameters. This algorithm is successively applied in continous optimization problems in literature such as stock price prediction, photovoltaic system optimization and cement compressive strength estimation but this study is the first attempt to apply this methodology in to discrete problems. Artificial rabbit optimization algorithm is used at the very beginning of the designed methodology, to obtain the initial population. The set of solutions (population) found in the last iteration of the artificial rabbit optimization algorithm constitute the initial population for the memetic algorithm based hyper heuristic. They go through evolutionary processes including crossover, mutation and hill climbing. In contrast to classical memetic algorithms, in hyper heuristic design algorithm components are applied with its alternatives and algorithm evolves to choose components that has better performance than alternatives. Hyper heuristic is defined as heuristics that choose heuristic from a predefined set of low level heuristics. In this study, the algorithm operators including crossover, mutation and hill climbing are considered as low level heuristics to be selected. Seven different operators are applied for crossover, and 5 different operators are applied for mutation and hill climbing. In addition to these operators, mutation rate and search depth (hill climbing parameter) parameters are also applied by considering 5 different options and considered as low level heuristic. The performance of each low level heuristic is represented with score values in meme structure, which is formed for each chromosome. This design allows to represent various algorithm configurations in one algorithm (4375 configurations in this research) and adapt itself to choose better low level heuristics through iterations. Applying hyper heuristic includes evolutionary processes with the race between low level heuristics. In each step after having an initial population from an artificial rabbit optimization algorithm, two parent chromosomes are selected with tournament selection (tour size equals 2). This means two randomly chosen individuals are selected and the one with better fitness value is referred to as parent. This selection is done twice to choose both of the parents. Parent chromosomes go into evolutionary process crossover, mutation and hill climbing. These operators are implemented with 7, 5 and 5 alternatives respectively. Depending on this, before applying any of these operators tournament selection (tour size is 2) is conducted. This means two of the operators are selected randomly and the one with a higher score is chosen. Scores for each operator are saved in meme structure which is tailored to each chromosome. Similarly, two of the algorithm parameters including mutation rate and depth search rate are included in meme structure with their five alternatives. Similar to operator selection, two of the five alternatives are selected and the one with higher score is implemented. After having finished the iteration, fitness values of parents and children are compared. If children's fitness is lower than parents (better solution obtained) then scores for each chosen operator and parameters are increased by one. This mechanism is called reinforcement learning in the literature. Designing algorithm components with alternatives and direct iteration process with feedback mechanism construct the main body of hyper heuristic algorithm. The performance criteria (objective function or fitness value) considered is the total completion time. Total completion time should be minimized and it is calculated by adding the completion time of each job on the last machine. Parameter optimization of the designed methodology is carried out using irace, an R-based algorithm configuration tool. The values of parameters such as population size, stopping criterion, and crossover rate are determined by irace. In addition to these parameters, irace also decides whether the initial population is generated using the Artificial Rabbit Optimization algorithm or produced randomly. The performance of the method is evaluated by solving a set of 270 benchmark problems, each repeated ten times. The test instances involve 2, 3, or 6 machines, with up to 16 groups and a maximum of 117 jobs. The results obtained are compared with those of two recently developed methods proposed by Cheng et al. (2021a) in the literature. The compared methods are a revised multi-start simulated annealing algorithm and its variant enhanced with a local search procedure. The Wilcoxon signed-rank test is used to calculate p values and evaluate whether the differences between the proposed method and the literature are statistically significant. Obtained results show that designed methodology has superior performance over revised multi start simulated annealing approach with the %73 of the instances and %33 of them is statistically significant. When compared with local search enhanced variant, designed methodology has better or equal results over %57 of instances. Overall, the crossover and mutation operators that demonstrate effective performance have been identified. Moreover, it is demonstrated that the modified crossover operations perform well. The superiority of the proposed methodology over the existing revised multi-start simulated annealing algorithm and its variant enhanced with local search is also proven.