  Local search is a widely used technique for tackling challenging optimization
problems, offering significant advantages in terms of computational efficiency
and exhibiting strong empirical behavior across a wide range of problem
domains. In this paper, we address a scheduling problem on two identical
parallel machines with the objective of \emph{makespan minimization}. For this
problem, we consider a local search neighborhood, called \emph{$k$-swap}, which
is a more generalized version of the widely-used \emph{swap} and \emph{jump}
neighborhoods. The $k$-swap neighborhood is obtained by swapping at most $k$
jobs between two machines in our schedule. First, we propose an algorithm for
finding an improving neighbor in the $k$-swap neighborhood which is faster than
the naive approach, and prove an almost matching lower bound on any such an
algorithm. Then, we analyze the number of local search steps required to
converge to a local optimum with respect to the $k$-swap neighborhood. For the
case $k = 2$ (similar to the swap neighborhood), we provide a polynomial upper
bound on the number of local search steps, and for the case $k = 3$, we provide
an exponential lower bound. Finally, we conduct computational experiments on
various families of instances, and we discuss extensions to more than two
machines in our schedule.
