Matching based very large-scale neighborhoods for parallel machine scheduling

T. Brueggemann, Johann L. Hurink

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
84 Downloads (Pure)


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 NP-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.
Original languageUndefined
Pages (from-to)637-658
Number of pages22
JournalJournal of heuristics
Issue number6
Publication statusPublished - Dec 2011


  • MSC-68M20
  • MSC-90B35
  • IR-78565
  • Scheduling · Parallel machines · Total weighted completion time · Verylarge-scale neighborhoods · Local search
  • METIS-281581
  • EWI-20836

Cite this