Waste management is a growing concern in the construction sector and particularly within demolition works. In order to encourage better management, the European Union has set up a minimal 70% recovering rate - in mass - for building and public works by 2020. And to help deconstruction companies to reach this aim without extra cost or delays, a Multi-Objective Optimization algorithm is suggested. The algorithm will work out a deconstruction strategy - i.e. type of waste treatment, number of required workers… - and will take into account three objectives - cost, delay and recovering rate - with 17 decision variables. Use on a real deconstruction situation highlights the interest of the algorithm. Eight optimization algorithms were tested and the most efficient algorithm is Decomposition-Based Evolutionary Algorithm. It came up with better strategies than the company one. This work proves that environmental performance can be improved without increasing cost or delay.