An iterated local search heuristic for multi-capacity bin packing and machine reassignment problems.
No Thumbnail Available
Date
2013
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Metaheuristics, Iterated local search, Multi-capacity bin packing, Machine reassignment
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: <http://www.sciencedirect.com/science/article/pii/S0957417413002030>. Acesso em: 16 jan. 2018.