# Matching based exponential neighborhoods for parallel machine scheduling

T. Brueggemann, Johann L. Hurink

Research output: Book/ReportReportProfessional

## Abstract

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 language Undefined Enschede University of Twente, Department of Applied Mathematics 18 0169-2690 Published - 2005

### Publication series

Name Memorandum Afdeling TW Department of Applied Mathematics, University of Twente 1773 0169-2690

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