Description

Les problèmes d’ordonnancement d’atelier constituent un enjeu majeur pour de nombreux secteurs industriels tels que l’automobile, l’aéronautique, les semi-conducteurs, la production pharmaceutique, les centres de tri ou la logistique hospitalière. Ils consistent à planifier l’exécution de tâches multi-opérations sous contraintes de ressources partagées, de précédence et de synchronisation. La combinatoire issue de ces contraintes rend ces problèmes particulièrement complexes, en particulier à l’échelle industrielle.
La littérature a largement étudié ces cadres (flow shop, job shop, open shop et leurs variantes flexibles, no-wait, no-idle ou blocking), mais demeure dominée par l’objectif de minimisation du makespan. Bien qu’utile pour les comparaisons méthodologiques, cet indicateur reflète imparfaitement les priorités industrielles, davantage orientées vers le flowtime, le retard (tardiness), la réduction des encours ou des formulations multi-objectifs. Les travaux portant sur ces critères réalistes sont peu nombreux et se limitent majoritairement à de petites instances, laissant ouverte la question essentielle du passage à l’échelle.
En parallèle, les méthodes de recherche arborescente heuristique (branch-and-bound avancé, guided search tree, beam search, hybridations) ont démontré leur efficacité sur de nombreux problèmes combinatoires de grande taille. Pourtant, leur utilisation systématique pour l’ordonnancement d’atelier avec objectifs non-makespan demeure encore marginale. Ce projet se situe précisément à cette convergence.
L’objectif principal est de développer des méthodes capables de résoudre efficacement des problèmes d’ordonnancement industriels de grande taille (nombre de tâches et nombre de machines) en se concentrant sur des objectifs réalistes : flowtime, retard, réduction des encours et approches multi-objectifs

Compétences requises

Le candidat devra avoir des connaissances et compétences solides en recherche opérationnelle, en optimisation combinatoire et en programmation. Des expériences d'usage de solveurs dans le cadre de projets seraient appréciées.

Bibliographie

Bennell, J.A., Song, X. A beam search implementation for the irregular shape packing problem. J Heuristics 16, 167–188 (2010). https://doi-org.sid2nomade-2.grenet.fr/10.1007/s10732-008-9095-x
C. Bierwirth, J. Kuhpfahl (2017), Extended GRASP for the job shop scheduling problem with total weighted tardiness objective, European Journal of Operational Research, Volume 261, Issue 3, Pages 835-848, https://doi.org/10.1016/j.ejor.2017.03.030.
E.G. Birgin, J.E. Ferreira, D.P. Ronconi (2020), A filtered beam search method for the m-machine permutation flowshop scheduling problem minimizing the earliness and tardiness penalties and the waiting time of the jobs, Computers & Operations Research, Volume 114, 104824, ISSN 0305-0548, https://doi.org/10.1016/j.cor.2019.104824.
Bürgy, R. A neighborhood for complex job shop scheduling problems with regular objectives. J Sched 20, 391–422 (2017). https://doi-org/10.1007/s10951-017-0532-2
Mao Chen, Yajing Yang, Zeyu Zeng, Xiangyang Tang, Xicheng Peng, Sannuya Liu (2024), A filtered beam search based heuristic algorithm for packing unit circles into a circular container, Computers & Operations Research, Volume 166, 106636, ISSN 0305-0548, https://doi.org/10.1016/j.cor.2024.106636.
Victor Fernandez-Viagas, Jose M. Framinan (2017), A beam-search-based constructive heuristic for the PFSP to minimise total flowtime, Computers & Operations Research, Volume 81, Pages 167-177, https://doi.org/10.1016/j.cor.2016.12.020.
Victor Fernandez-Viagas, Jorge M.S. Valente, Jose M. Framinan (2018), Iterated-greedy-based algorithms with beam search initialization for the permutation flowshop to minimise total tardiness, Expert Systems with Applications, Volume 94, Pages 58-69, https://doi.org/10.1016/j.eswa.2017.10.050.
J. Kuhpfahl, C. Bierwirth (2016), A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective, Computers & Operations Research, Volume 66, Pages 44-57, https://doi.org/10.1016/j.cor.2015.07.011.
Li, Z., Janardhanan, M. N., & Rahman, H. F. (2021). Enhanced beam search heuristic for U-shaped assembly line balancing problems. Engineering Optimization, 53(4), 594–608. https://doi.org/10.1080/0305215X.2020.1741569
Zixiang Li, Ibrahim Kucukkoc, Qiuhua Tang (2021), Enhanced branch-bound-remember and iterative beam search algorithms for type II assembly line balancing problem, Computers & Operations Research, Volume 131, 2021, 105235, ISSN 0305-0548, https://doi.org/10.1016/j.cor.2021.105235.
Luc Libralesso, Pablo Andres Focke, Aurélien Secardin, Vincent Jost (2022), Iterative beam search algorithms for the permutation flowshop, European Journal of Operational Research, Volume 301, Issue 1, Pages 217-234, ISSN 0377-2217, https://doi.org/10.1016/j.ejor.2021.10.015.
Yazid Mati, Stèphane Dauzère-Pérès, Chams Lahlou (2011), A general approach for optimizing regular criteria in the job-shop scheduling problem, European Journal of Operational Research, Volume 212, Issue 1, Pages 33-42, https://doi.org/10.1016/j.ejor.2011.01.046.
Rafael Morais, Teobaldo Bulhões, Anand Subramanian (2024), Exact and heuristic algorithms for minimizing the makespan on a single machine scheduling problem with sequence-dependent setup times and release dates, European Journal of Operational Research, Volume 315, Issue 2, Pages 442-453, ISSN 0377-2217, https://doi.org/10.1016/j.ejor.2023.11.024.
Consuelo Parreño-Torres, Ramon Alvarez-Valdes, Francisco Parreño (2022), A beam search algorithm for minimizing crane times in premarshalling problems, European Journal of Operational Research, Volume 302, Issue 3, Pages 1063-1078, ISSN 0377-2217, https://doi.org/10.1016/j.ejor.2022.01.038.
Rossi, F.L., Nagano, M.S. Beam search-based heuristics for the mixed no-idle flowshop with total flowtime criterion. OR Spectrum 44, 1311–1346 (2022).
https://doi.org.sid2nomade-2.grenet.fr/10.1007/s00291-022-00678-9
Oleh Sobeyko, Lars Mönch (2016), Heuristic approaches for scheduling jobs in large-scale flexible job shops, Computers & Operations Research, Volume 68, Pages 97-109, https://doi.org/10.1016/j.cor.2015.11.004.

Mots clés

Ordonnancement, Fonction objective industrielle, Recherche opérationnelle, Recherche arborescente, Méthodes heuristiques, Optimisation Combinatoire