Matching based exponential neighborhoods for parallel machine scheduling

T. Brueggemann, Johann L. Hurink

Research output: Book/ReportReportProfessional

50 Downloads (Pure)


We study the minimum total weighted completion time problem on parallel machines, which is known to be strongly $\mathcal{NP}$-hard. We develop general ideas leading to exponential neighborhoods in which the best improving neighbor can be determined by calculating a maximum weighted matching of an improvement graph. In a second step we introduce neighborhoods that form the base for the exponential neighborhoods.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente
Number of pages18
ISBN (Print)0169-2690
Publication statusPublished - 2005

Publication series

NameMemorandum Afdeling TW
PublisherDepartment of Applied Mathematics, University of Twente
ISSN (Print)0169-2690


  • MSC-68M20
  • MSC-90B35
  • IR-65957
  • METIS-225433
  • EWI-3593

Cite this