Simulated annealing for the machine reassignment problem

Gabriel M. Portal (), Marcus Ritt (), Leonardo M. Borba () and Luciana S. Buriol ()
Additional contact information
Gabriel M. Portal: Google Inc.
Marcus Ritt: Universidade Federal do Rio Grande do Sul
Leonardo M. Borba: Universidade Federal do Rio Grande do Sul
Luciana S. Buriol: Universidade Federal do Rio Grande do Sul

Annals of Operations Research, 2016, vol. 242, issue 1, No 5, 93-114

Abstract: Abstract Given an initial assignment of processes to machines, the machine reassignment problem is to find an assignment that improves the machine usage, subject to several resource and allocation constraints, and considering reassignment costs. We propose a heuristic based on simulated annealing for solving this problem. It uses two neighborhoods, one that moves a process from one machine to another, and a second one that swaps two processes on different machines. We present data structures that permit to validate and execute a move in time $$O(r+d)$$ O ( r + d ) where $$r$$ r is the number of resources and $$d$$ d the number of dependencies of the service the process belongs to. The heuristic runs with two different sets of parameters in parallel until a convergence criterion is satisfied. The machine reassignment problem was subject of the ROADEF/EURO challenge in 2012, and the proposed algorithm ranked fourth in the final round of the senior category of the competition.

Keywords: Machine reassignment; Scheduling; Simulated annealing (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-014-1771-7 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-014-1771-7

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

DOI: 10.1007/s10479-014-1771-7

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 ().