Matching based very large‐scale neighborhoods for parallel machine scheduling

In this paper we study very large‐scale neighborhoods for the minimum total weighted completion time problem on parallel machines, which is known to be strongly $\mathrm{𝒩𝒫}$ ‐hard. We develop two different ideas leading to very large‐scale neighborhoods in which the best improving neighbor can be determined by calculating a weighted matching. The first neighborhood is introduced in a general fashion using combined operations of a basic neighborhood. Several examples for basic neighborhoods are given. The second approach is based on a partitioning of the job sets on the machines and a reassignment of them. In a computational study we evaluate the possibilities and the limitations of the presented very large‐scale neighborhoods.