Cette thèse porte sur la conception et l'implémentation d'algorithmes approchés pour l'optimisation en variables discrètes. Plus particulièrement, dans cette étude nous nous intéressons à la résolution de trois problèmes combinatoires difficiles : le « Bin-Packing », la « Réaffectation de machines » et la « Gestion des rames sur les sites ferroviaires ». Le premier est un problème d'optimisation classique et bien connu, tandis que les deux autres, issus du monde industriel, ont été proposés respectivement par Google et par la SNCF. Pour chaque problème, nous proposons une approche heuristique basée sur la recherche locale et nous comparons nos résultats avec les meilleurs résultats connus dans la littérature. En outre, en guise d'introduction aux méthodes de recherche locale mise en œuvre dans cette thèse, deux métaheuristiques, GRASP et Recherche Tabou, sont présentées à travers leur application au problème de la couverture minimale.

Sažetak U ovom radu je obrađen problem upravljanja energijom velikih razmjera (eng. Large Scale Energy Management - LSEM), sa dva tipa elektrana (termalne i nuklearne). Elektrane prvog tipa mogu istovremeno proizvoditi energiju i snabdijevati se gorivom. Elektrane drugog tipa su nuklearne elektrane koje se s vremena na vrijeme moraju isključiti radi snabdijevanja gorivom i održavanja. LSEM je problem optimizacije proizvodnje elektrana oba tipa i raspoređivanja prekida u radu nuklearnih elektrana s ciljem postizanja minimalnih troškova proizvodnje. Predstavljena je heuristika zasnovana na tehnici lokalne pretrage (eng. Local Search - LS) i uslovnom programiranju (eng. Constraints Satisfaction Programming - CSP). Predstavljeni su i rezultati za neke realne instance problema.

This paper presents a heuristic approach combining constraint satisfaction, local search and a constructive optimization algorithm for a large-scale energy management and maintenance scheduling problem. The methodology shows how to successfully combine and orchestrate different types of algorithms and produce competitive results. The local search for production assignment is a simple yet optimal solution for the relaxed initial problem. We also propose an efficient way to scale the method for huge instances. A large part of the presented work is done to compete in the ROADEF/EURO Challenge 2010, organized jointly by the ROADEF, EURO and the Électricité de France. The numerical results obtained for the official competition instances testify about the quality of the approach. The method achieves 3 out of 15 possible best results.