Fast machine reassignment

Franck Butelle (), Laurent Alfandari (), Camille Coti (), Lucian Finta (), Lucas Létocart (), Gérard Plateau (), Frédéric Roupin (), Antoine Rozenknop () and Roberto Wolfler Calvo ()
Additional contact information
Franck Butelle: Université Paris 13, Sorbonne Paris Cité
Laurent Alfandari: Université Paris 13, Sorbonne Paris Cité
Camille Coti: Université Paris 13, Sorbonne Paris Cité
Lucian Finta: Université Paris 13, Sorbonne Paris Cité
Lucas Létocart: Université Paris 13, Sorbonne Paris Cité
Gérard Plateau: Université Paris 13, Sorbonne Paris Cité
Frédéric Roupin: Université Paris 13, Sorbonne Paris Cité
Antoine Rozenknop: Université Paris 13, Sorbonne Paris Cité
Roberto Wolfler Calvo: Université Paris 13, Sorbonne Paris Cité

Annals of Operations Research, 2016, vol. 242, issue 1, No 7, 133-160

Abstract: Abstract This paper proposes a new method for solving the Machine Reassignment Problem in a very short computational time. The problem has been proposed by Google as subject of the Challenge ROADEF/EURO 2012. The Machine Reassignment Problem consists in looking for a reassignment of processes to machines in order to minimize a complex objective function, subject to a rich set of constraints including multidimensional resource, conflict and dependency constraints. In this study, a cooperative search approach is presented for machine reassignment. This approach uses two components: Adaptive Variable Neighbourhood Search and Simulated Annealing based Hyper-Heuristic, running in parallel on two threads and exchanging solutions. Both algorithms employ a rich set of heuristics and a learning mechanism to select the best neighborhood/move type during the search process. The cooperation mechanism acts as a multiple restart which gets triggered whenever a new better solution is achieved by a thread and then shared with the other thread. Computational results on the Challenge instances as well as instances of a Generalized Assignment-like problem are given to show the relevance of the chosen methods and the high benefits of cooperation.

Keywords: Generalized Assignment; Adaptive Variable Neighborhood Search; Simulated Annealing; Hyper-Heuristic; Cooperative Parallel Search (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-015-2082-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:242:y:2016:i:1:d:10.1007_s10479-015-2082-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-015-2082-3

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().