Abstract: Memetic Algorithms are hybridizations of Evolutionary Algorithms (AEs) with problem-specific heuristics or other meta-heuristics, that are generally used within the EA to locally improve the evolutionary solutions. However, this approach fails when the local method stops working on the complete problem. Divide-and-Evolve is an original approach that evolutionarily builds a sequential slicing of the problem at hand into several, hopefully easier, sub-problems: the embedded (meta-)heuristic is only asked to solve the 'small' problems, and Divide-and-Evolve is thus able to globally solve problems that are intractable when directly fed into the heuristic. The Divide-and-Evolve approach is described here in the context of Temporal Planning Problems (TPPs), and the results on the standard Zeno transportation benchmarks demonstrate its ability to indeed break the complexity barrier. But an even more prominent advantage of the Divide-and-Evolve approach is that it immediately opens up an avenue for multi-objective optimization, even when using single-objective embedded algorithm.