# A Hybrid Discrete Memetic Algorithm for Solving Flow-Shop Scheduling Problems
###### Abstract
The BMEA was later successfully extended also to discrete problems, like, among others, the flow-shop scheduling problem itself, produced considerably better efficiency for some problems. A novel hybrid algorithm version with a BEA wrapper and nested SA showed remarkably good results on numerous benchmarks [3]. As discussed above, initially, the combination of bacterial evolutionary algorithms with local search methods was proposed only for the very special aim of increasing the ability to find the optimal estimation of fuzzy rules. In the original BEA paper, mechanical, chemical, and electrical engineering problems were presented as benchmark applications. In addition, a fascinating mathematical research field, namely, solving transcendental functions, completed the list of first applications. In the first version of BMEA, where the local search method applied was the second-order gradient method, the Levenberg-Marquard [14] algorithm was tested on all these benchmarks. The benchmark tests with the BMEA obtained better results than any former ones in the literature and outscored all other approaches used to estimate the parameters of the trapezoidal fuzzy membership functions [15]. Later, first-order gradient-based algorithms were also investigated as local search, which seemed promising [11]. In the next, the idea of BMEA was extended towards discrete problems, where gradient-based local search was replaced by traditional discrete optimization, such as exhaustive search, unbounded sub-graphs. This new family of algorithms was named discrete bacterial memetic evolutionary algorithms (DBMEA). DBMEA algorithms were first tested on various extensions of the travelling salesman problem and produced rather promising results. DBMEA algorithms have also been investigated on discrete permutation-based problems, where the local search methods were matching bounded discrete optimization techniques. In a GA-based discrete memetic type approach, _n-opt_ local search algorithms were suggested by [PERSON] et al. [16]. The investigations with simulations reduced the algorithms to the consecutive running 2-opt and 3-opt methods. In the case of \(n\geq 4\), the computational time was too high, thus limiting the pragmatical usability of the algorithm. The 2-opt algorithm was first applied to solve various routing problems [17], where in the bounded sub-graph, two graph edges were always swapped in the local search phase. It is worth noting that 3-opt [18] is similar to the 2-opt operator; here, three edges are always deletedand replaced in a single step, which results in seven different ways to reconnect the graph, in order to find the local optimum. In this research, another class of discrete optimization problems, the flow-shop, came to focus. Thus, in the next Section 2, the paper will give a detailed explanation of the flow-shop scheduling problem. Section 3 is a detailed survey of commonly used classic and state-of-the-art algorithms. The algorithms used by the novel HDBMEA algorithm proposed in this paper will be detailed in Sections 4-6. Section 7 deals with the results from the Taillard flow-shop benchmark set and with the comparison to relevant algorithms selected from Section 3. Section 8 extensively analyses each parameter's impact on the HDBMEA algorithm's scheduling performance and run-time. The result of our analysis is a chosen parameter set with which we prove the abilities of our proposed algorithm.