Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916496424304640 |
|---|---|
| author | Rohwedder, Lars Safari, Ashkan Vredeveld, Tjark |
| author_facet | Rohwedder, Lars Safari, Ashkan Vredeveld, Tjark |
| contents | Local search is a widely used technique for tackling challenging optimization problems, offering simplicity and strong empirical performance across various 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, by considering a local search neighborhood, called $k$-swap. A $k$-swap neighbor is obtained by interchanging the machine allocations of at most $k$ jobs scheduled on two machines. While local search algorithms often perform well in practice, they can exhibit poor worst-case performance. In our previous study, we showed that for $k \geq 3$, there exists an instance where the number of iterations required to converge to a local optimum is exponential in the number of jobs. Motivated by this discrepancy between theoretical worst-case bound and practical performance, we apply smoothed analysis to the $k$-swap local search. Smoothed analysis has emerged as a powerful framework for analyzing the behavior of algorithms, aiming to bridge the gap between poor worst-case and good empirical performance. In this paper, we show that the smoothed number of iterations required to find a local optimum with respect to the $k$-swap neighborhood is bounded by $O(m^2 \cdot n^{2k+2} \cdot \log m \cdot ϕ)$, where $n$ and $m$ are the numbers of jobs and machines, respectively, and $ϕ\geq 1$ is the perturbation parameter. The bound on the smoothed number of iterations demonstrates that the proposed lower bound reflects a pessimistic scenario which is rare in practice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_17245 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling Rohwedder, Lars Safari, Ashkan Vredeveld, Tjark Data Structures and Algorithms Local search is a widely used technique for tackling challenging optimization problems, offering simplicity and strong empirical performance across various 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, by considering a local search neighborhood, called $k$-swap. A $k$-swap neighbor is obtained by interchanging the machine allocations of at most $k$ jobs scheduled on two machines. While local search algorithms often perform well in practice, they can exhibit poor worst-case performance. In our previous study, we showed that for $k \geq 3$, there exists an instance where the number of iterations required to converge to a local optimum is exponential in the number of jobs. Motivated by this discrepancy between theoretical worst-case bound and practical performance, we apply smoothed analysis to the $k$-swap local search. Smoothed analysis has emerged as a powerful framework for analyzing the behavior of algorithms, aiming to bridge the gap between poor worst-case and good empirical performance. In this paper, we show that the smoothed number of iterations required to find a local optimum with respect to the $k$-swap neighborhood is bounded by $O(m^2 \cdot n^{2k+2} \cdot \log m \cdot ϕ)$, where $n$ and $m$ are the numbers of jobs and machines, respectively, and $ϕ\geq 1$ is the perturbation parameter. The bound on the smoothed number of iterations demonstrates that the proposed lower bound reflects a pessimistic scenario which is rare in practice. |
| title | Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.17245 |