Por favor, use este identificador para citar o enlazar este ítem:
http://www.repositorio.ufop.br/jspui/handle/123456789/9375
Título : | An iterated local search heuristic for multi-capacity bin packing and machine reassignment problems. |
Autor : | Masson, Renaud Vidal, Thibaut Victor Gaston Michallet, Julien Penna, Puca Huachi Vaz Petrucci, Vinicius Subramanian, Anand Dubedout, Hugues |
Palabras clave : | Metaheuristics Iterated local search Multi-capacity bin packing Machine reassignment |
Fecha de publicación : | 2013 |
Citación : | MASSON, 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. |
Resumen : | This 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. |
URI : | http://www.repositorio.ufop.br/handle/123456789/9375 |
metadata.dc.identifier.uri2: | http://www.sciencedirect.com/science/article/pii/S0957417413002030 |
metadata.dc.identifier.doi: | https://doi.org/10.1016/j.eswa.2013.03.037 |
ISSN : | 0957-4174 |
Aparece en las colecciones: | DECOM - Artigos publicados em periódicos |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
ARTIGO_ItaredLocalSearch.pdf Restricted Access | 997,81 kB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.