2-Dimensional packing on a variable size rectangular interface. (March 2023)

• Record Type: Journal Article
• Authors: Kacem, Imed; Kadri, Ilyes; Martin, Benoît; Pecci, Isabelle
• Is Part Of: Computers & industrial engineering. Volume 177(2023)
• Publication Date: 2023-03
• Subjects: Genetic algorithm -- Heuristic -- Integer linear programming -- Two-dimensional bin packing -- User interface; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2023.109022
• Languages: English
• ISSNs: 0360-8352

Abstract

Abstract: The purpose of this work is to propose effective approximate algorithms capable to generate, in a very short time, a feasible 2-dimensional configuration (or interface) containing a set of given menus (or items) adapted to a certain user context (physical activity for example). The proposed approach should yield good configurations, with the aim of minimizing the used surface, which can be seen as a variable-size bin. The dimensions of such a bin should respect a fixed ratio between its width and its height. To solve the problem, we propose different approaches based on the shelf strategy. Moreover, we elaborate two genetic algorithms, which we compare to an integer linear programming model. The exact resolution of this mathematical model gives an optimal solution only for small instances. For the other instances, it is difficult to reach the optimal value in a short running time, which shows the practical interest of the proposed approximate methods. Highlights: A single variable size two-dimensional bin packing. Two genetic algorithms for minimizing the used area. Heuristics based on shelf rules with reduced time complexity. Numerical testing and comparison with the obtained optimal solutions using CPLEX.