Abstract. Within the development of physical products, manufacturing and assembly deviations have to be taken into account. To assure functional fulfilment, tolerances are defined in the detailed design phase of mechanical engineering to specify allowed errors in dimension, shape and position of the manufactured product. For the early detection of possible problems, statistical tolerance analysis software generates non-ideal parts which have to be repositioned within their assembly because of their non-ideal build. This process is called "relative positioning". We perform this task by using heuristic optimization methods. Because of the high computational requirements for the evaluation of part positions (collision detection, distance computation, tolerance fulfilment etc.), several acceleration methods are suggested and analyzed experimentally.