The normalization of semi-formal modeling methods, such as the UML, leads to re-visit the problem of early OO integration test planning. Integration is often conducted under some incremental steps. Integration test planning aims at ordering the components to be integrated and tested in relationships with the already tested part of the system. This paper presents a modeling of the test integration problem from a UML design, then details existing integration strategies and proposes two integration strategies: a deterministic one called Triskell and an original semi-random one, based on genetic algorithms called Genetic. Strategies are compared in detail (algorithmic cost and optimization choices) and a large part of the paper is dedicated to an experimental comparison of each strategy on 6 real-world case studies of various complexities (from a “small” telecommunication software to the Swing Java library). Results show that a good modeling of this optimization problem associated with well-chosen algorithms induce a significant gain in terms of testing effort and duration.