A k-swap local search for makespan scheduling
研究了在相同并行机调度中最小化最大完工时间的问题，提出了一种比朴素方法更快的k-交换邻域改进算法，并分析了收敛到局部最优的步数，对k≥3给出指数下界，对k=2（两台机器）给出多项式上界。
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 the problem of scheduling a set of jobs on identical parallel machines with the objective of makespan minimization . For this problem, we consider a local search neighborhood, called k - swap , which is a generalized version of the widely-used swap and jump neighborhoods. The k -swap neighborhood is obtained by swapping at most k jobs between two machines. 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 k ≥ 3 , we provide an exponential lower bound regardless of the number of machines, and for k = 2 (similar to the swap neighborhood), we provide a polynomial upper bound for the case of having two machines. Finally, we conduct computational experiments on various families of instances.