Very Large-Scale Neighborhoods with Performance Guarantees for Minimizing Makespan on Parallel Machines

T. Brueggemann, Johann L. Hurink, T. Vredeveld, Gerhard Woeginger

Research output: Book/ReportReportProfessional

108 Downloads (Pure)


We study the problem of minimizing the makespan on m parallel machines. We introduce a very large-scale neighborhood of exponential size (in the number of machines) that is based on a matching in a complete graph. The idea is to partition the jobs assigned to the same machine into two sets. This partitioning is done for every machine with some chosen rule to receive 2m parts. A new assignment is received by putting to every machine exactly two parts. The neighborhood Nsplit consists of all possible rearrangements of the parts to the machines. The best assignment of Nsplit can be calculated in time O(mlogm) by determining the perfect matching having minimum maximal edge weight in an improvement graph, where the vertices correspond to parts and the weights on the edges correspond to the sum of the processing times of the jobs belonging to the parts. Additionally, we examine local optima in this neighborhood and in combinations with other neighborhoods. We derive performance guarantees for these local optima.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages17
Publication statusPublished - 2006

Publication series

NameMemorandum Faculty of Mathematical Sciences
PublisherDepartment of Applied Mathematics, University of Twente
ISSN (Print)0169-2690


  • IR-66526
  • MSC-68W25
  • METIS-238241
  • EWI-7591
  • MSC-90B35

Cite this