[Talks@IDSIA] 08.11 1130 M Dell'Amico: A batching moves iterated local search algorithm for the bin packing problem with generalized precedence constraints

08 Nov 1130-1200 IDSIA meeting room, Galleria 1, Manno Prof Mauro Dell'Amico University of Modena and Reggio Emilia, Italy Title: A batching moves iterated local search algorithm for the bin packing problem with generalized precedence constraints Abstract: We propose a generalization of the bin packing problem, obtained by adding precedences between items that can assume heterogeneous non-negative integer values. Such generalization also models the well-known Simple Assembly Line Balancing Problem of type I. To solve the problem we introduce a simple and effective iterated local search algorithm that integrates two constructive procedures and four neighborhood 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. (joint work with R. Kramer and M. Iori)