A batching-move iterated local search algorithm for the bin packing problem with generalized precedence constraints

Abstract

In this paper, we propose a generalisation of the bin packing problem, obtained by adding precedences between items that can assume heterogeneous non-negative integer values. Such generalisation also models the well-known Simple Assembly Line Balancing Problem of type I. To solve the problem, we propose a simple and effective iterated local search algorithm that integrates in an innovative way of constructive procedures and neighbourhood structures to guide the search to local optimal solutions. Moreover, we apply some preprocessing procedures and adapt classical lower bounds from the literature. Extensive computational experiments on benchmark instances suggest that the developed algorithm is able to generate good quality solutions in a reasonable computational time.

Keywords:

• bin packing
• assembly line balancing
• generalised precedence constraints
• iterated local search
• batching moves

Acknowledgements

We thank Alena Otto for kindly providing us with new instances for the SALBP-I, Tom Pape for giving additional details about his work, Jordi Pereira for updating us with new results for the BPP-P, and two anonymous referees for comments that improved the quality of the paper.

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research was partially supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq/Brazil) [grant number GDE 201222/2014-0]; Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior (CAPES/Brazil) [grant PVE number A007/2013].