PhD in Advanced hybridization of metaheuristics and constraint programming techniques for the integration of energy constraints in assembly line balancing problems

Location : Laboratory of Informatics, Modelling and Optimization of the Systems (LIMOS UMR CNRS 6158) – Campus des Cézeaux – 1 rue de la Cherbade, 63178 Aubière

Supervision : Laurent Deroussi (LIMOS, co-supervisor) Nathalie Grangeon (LIMOS, co-supervisor)MatthieuPy(LIMOS) Fouad Riane (Ecole Centrale de Casablanca)

Contacts : {laurent.deroussi,nathalie.grangeon}@uca.fr

Context of the thesis :

This thesis is part of the IRC ITPS (International Research Centre on Innovative Transportation and Production Systems) framework and focuses on the problem of robotic assembly lines balancing problems, an area of interest for the LIMOS, which has been investing resources in this field for several years, as evidenced by works such as (Gourgand et al., 2007), (Grangeon et al., 2011), (Grangeon et al., 2012), as well as more recent contributions such as the thesis of Youssef Lahrichi (Lahrichi, 2021) or the Master's internship of Arnauld Tuyaba (Tuyaba et al., 2023). While traditional assembly line balancing problems typically focus on minimizing the number of workstations or the cycle time, the laboratory, as part of Arnauld Tuyaba's Master's internship, became interested in considering the energy constraints and objectives that may exist in this issue. This involved proposing solutions to the studied problem that aim to minimize peak energy consumption. Investigating this matter introduces an additional degree of complexity to the problem under study because it involves addressing a highly constrained combinatorial optimization problem with a level of detail more significant than commonly studied variants.

Objective and anticipated methods:

The objective of this thesis is to propose innovative methods for studying assembly line balancing problems that take into account energy constraints. In particular, we will investigate the contribution of constraint programming to this theme and explore a less common form of hybridization between metaheuristics and constraint programming. We believe that this form of hybridization can prove to be very effective in solving optimization problems that decompose into sub-problems, at least one of which is a feasibility problem or a highly constrained problem for which it is difficult to find solutions satisfying all constraints of the problem. We will focus particularly on hybridizations with the boolean satisfiability problem (Biere et al., 2021) or with the constraint satisfaction problem (Ghedira, 2013).

The work could be structured as follows:

• A literature review on energy constraints in scheduling and assembly line balancing problems,
• A literature review on hybridization techniques of metaheuristics with mathematical programming techniques,
• The design of a hybrid algorithm, which would combine the advantages of metaheuristics and constraint programming.
• The implementation of this method to solve an assembly line balancing problem with energy constraints.

References:

M. Gourgand, N. Grangeon, S. Norre, Metaheuristics based on bin packing for the line balancing problem, RAIRO OR, Vol 41, n°2, pages 193-211, 2007.

N. Grangeon, P. Leclaire, S. Norre, Heuristics for the re-balancing of a vehicle assembly line, International Journal of Production Research, Volume 49, Issue 22, pages 6609-6628, 2011.

N. Grangeon, S. Norre, Extending metaheuristics based on bin packing for SALBP to PALBP, EJIE (European Journal of Industrial Engineering), Vol 6, n°6, pages 713-732, 2012. 

Y. Lahrichi, Balancing reconfigurable or robotic assembly lines : exact and hybrid methods, 2021

Tuyaba, L. Deroussi, N. Grangeon, S. Norre (2023) Prise en compte de la consommation énergétique dans l’équilibrage de lignes d’assemblage, ROADEF

Armin Biere, Marijn Heule, Hans van Maaren, Toby Walsh (2021). “Handbook of Satisfiability – Second Edition”, Frontiers in Artificial Intelligence and Applications, Volume 336.

Ghedira, Khaled, “Constraint Satisfaction Problems: CSP Formalisms and Techniques”, 2013.