A stochastic method for planning decomposition, called Divide-and-Evolve, that was introduced recently and which focuses on plan quality. The basic principle is to search the space of state decompositions of the planning problem at hand by means of artificial evolution: candidate solutions are sequences of intermediate goals which define consecutive planning subproblems that are hopefully easier to solve than the global problem. The scope of Divide-and-Evolve is temporal planning as defined by PDDL2.1 (the widely adopted planning domain description language standard) where the problems are described using durative actions and where plan quality is the total makespan.