## 1 Introduction  
The endeavor of developing a suitable neighborhood scheme is a key factor in the success of any local search algorithm. The reason is that the critical role the size of the neighborhood plays in striking a balance between the effectiveness and computational time [1, 2]. For striking such a balance in solving the permutation flow-shop scheduling problem, this paper presents a two-level decomposition-based, variable neighborhood search stochastic algorithm that embeds a large neighborhood scheme into a small one. The algorithm, called Refining Decomposition-based Integrated Search (RDIS), refines a solution obtained by its small neighborhood search through its large neighborhood search, and uses the notion of decomposition in the two levels of (i) producing an initial solution, and (ii) performing large neighborhood search on the initial solution. Both neighborhood schemes employed are k-exchange [3]. The \(k\)-exchange schemes, as the most common types of neighborhood schemes, consider two candidate solutions as neighbors if they differ in at most \(k\) solution elements [3]. It is clear that larger neighborhood schemes contain more and potentially better candidate solutions but this increases the neighborhood size of these schemes exponentially with \(k\)[2]. In effect, when \(k\) is as large as the size of the problem, the corresponding neighborhood scheme makes local optimal solutions global optimal; however, because of their impracticality, these kinds of neighborhood schemes are not used in practice. On the other hand, smaller values of \(k\) require lower computational time at the cost of generating fewer candidate solutions [1; 3]. In combing small and large neighborhood schemes, the RDIS has three synergetic characteristics of (i) generating an initial solution with a construction method that has been built upon the concept of decomposition of jobs and the extended two-machine solution strategy, (ii) improving the initial solution with a small neighborhood search, and (iii) enhancing the result produced by the small-neighborhood search with a large neighborhood search which has been built based on a decomposition technique. The construction method for generating initial solutions is based on the recursive application of the extended 2-machine problem [4], described in Section 2. Aimed at generating high-quality solutions, and inspired by the famous two-machine problem [4], this recursive algorithm repeatedly decomposes the jobs and finds the best permutation for the decomposed jobs, with the goal of improving the quality of initial solutions. Although the employed large neighborhood search, the same as the engaged construction method, is based on decomposition, it performs decomposition in an iterative manner, and not recursively. This iterative decomposition technique starts with the top \(k\) jobs in the permutation and ends with the \(k\) bottom jobs, ignoring any unfruitful contiguous parts in the middle. In each round, it also keeps the result of calculations in memory to prevent any repeat of calculations in further rounds. In optimizing small chunks, this effective use of memory makes the optimization process as fast as simple decoding of a permutation to a solution. The main contributions of this paper are outlined in the following:  
* The effective embedding of a large neighborhood decomposition technique into a variable neighborhood search for the permutation flow-shop scheduling problem;
* Efficient decomposition of the main problem into subproblems, and finding optimal permutations for those smaller subproblems; and
* Employing the concept of the critical path, as described in Section 4, in the employed large neighborhood search. The paper is structured as follows. In Section 2, the related work is discussed, and Section 3 presents the formulation of the permutation flow-shop scheduling problem. Section 4 presents the RDIS and provides a stepwise description of the corresponding algorithm. In Section 5, the results of computational experiments are discussed.