Please use this identifier to cite or link to this item:
Title: An iterated local search heuristic for multi-capacity bin packing and machine reassignment problems.
Authors: Masson, Renaud
Vidal, Thibaut Victor Gaston
Michallet, Julien
Penna, Puca Huachi Vaz
Petrucci, Vinicius
Subramanian, Anand
Dubedout, Hugues
Keywords: Metaheuristics
Iterated local search
Multi-capacity bin packing
Machine reassignment
Issue Date: 2013
Citation: 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: <>. Acesso em: 16 jan. 2018.
Abstract: 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.
ISSN: 0957-4174
Appears in Collections:DECOM - Artigos publicados em periódicos

Files in This Item:
File Description SizeFormat 
ARTIGO_ItaredLocalSearch.pdf997,81 kBAdobe PDFView/Open    Request a copy

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.