Smoothed analysis of the k-swap neighborhood for makespan scheduling

In this paper, we address the problem of scheduling a set of n jobs on m identical parallel machines with the objective of makespan minimization, by considering a local search neighborhood, called k-swap. In our previous study, we provided an exponential lower bound of 2^Ω(n) for k≥3. In this study, we show that the smoothed number of iterations in finding a local optimum with respect to the k-swap neighborhood is O(m²⋅n^2k+2⋅log⁡m⋅ϕ), where ϕ≥1 is the perturbation parameter.