Matching based very large-scale neighborhoods for parallel machine scheduling

作者：Brueggemann Tobias; Hurink Johann L^*

来源：Journal of Heuristics, 2011, 17(6): 637-658.

DOI：10.1007/s10732-010-9149-8

• Scheduling
• Parallel machines
• Total weighted completion time
• Very large-scale neighborhoods
• Local search

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.

• 出版日期2011-12