An iterated local search heuristic for multi-capacity bin packing and machine reassignment problems.

Simple item page
dc.contributor.authorMasson, Renaud
dc.contributor.authorVidal, Thibaut Victor Gaston
dc.contributor.authorMichallet, Julien
dc.contributor.authorPenna, Puca Huachi Vaz
dc.contributor.authorPetrucci, Vinicius
dc.contributor.authorSubramanian, Anand
dc.contributor.authorDubedout, Hugues
dc.date.accessioned2018-01-30T13:10:37Z
dc.date.available2018-01-30T13:10:37Z
dc.date.issued2013
dc.description.abstractThis paper proposes an efficient Multi-Start Iterated Local Search for Packing Problems (MS-ILS-PPs) metaheuristic for Multi-Capacity Bin Packing Problems (MCBPP) and Machine Reassignment Problems (MRP). The MCBPP is a generalization of the classical bin-packing problem in which the machine (bin) capacity and task (item) sizes are given by multiple (resource) dimensions. The MRP is a challenging and novel optimization problem, aimed at maximizing the usage of available machines by reallocating tasks/processes among those machines in a cost-efficient manner, while fulfilling several capacity, conflict, and dependency-related constraints. The proposed MS-ILS-PP approach relies on simple neighborhoods as well as problem-tailored shaking procedures. We perform computational experiments on MRP benchmark instances containing between 100 and 50,000 processes. Near-optimum multi-resource allocation and scheduling solutions are obtained while meeting specified processing-time requirements (on the order of minutes). In particular, for 9/28 instances with more than 1000 processes, the gap between the solution value and a lower bound measure is smaller than 0.1%. Our optimization method is also applied to solve classical benchmark instances for the MCBPP, yielding the best known solutions and optimum ones in most cases. In addition, several upper bounds for non-solved problems were improved.pt_BR
dc.identifier.citationMASSON, R. et al. An iterated local search heuristic for multi-capacity bin packing and machine reassignment problems. Expert Systems with Applications, v. 40, p. 5266-5275, 2013. Disponível em: <http://www.sciencedirect.com/science/article/pii/S0957417413002030>. Acesso em: 16 jan. 2018.pt_BR
dc.identifier.doihttps://doi.org/10.1016/j.eswa.2013.03.037
dc.identifier.issn0957-4174
dc.identifier.urihttp://www.repositorio.ufop.br/handle/123456789/9375
dc.identifier.uri2http://www.sciencedirect.com/science/article/pii/S0957417413002030pt_BR
dc.language.isoen_USpt_BR
dc.rightsrestritopt_BR
dc.subjectMetaheuristicspt_BR
dc.subjectIterated local searchpt_BR
dc.subjectMulti-capacity bin packingpt_BR
dc.subjectMachine reassignmentpt_BR
dc.titleAn iterated local search heuristic for multi-capacity bin packing and machine reassignment problems.pt_BR
dc.typeArtigo publicado em periodicopt_BR
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
ARTIGO_ItaredLocalSearch.pdf
Size:
997.81 KB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
924 B
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
DECOM - Artigos publicados em periódicos