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

63 Downloads (Pure)

Abstract

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
No.1801
ISSN (Print)0169-2690

Keywords

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

Cite this

Brueggemann, T., Hurink, J. L., Vredeveld, T., & Woeginger, G. (2006). Very Large-Scale Neighborhoods with Performance Guarantees for Minimizing Makespan on Parallel Machines. (Memorandum Faculty of Mathematical Sciences; No. 1801). Enschede: University of Twente, Department of Applied Mathematics.