Do not use frame rate to measure time. Use time to measure time. GC skipping can take 3/10 seconds, other tasks can run in the background, etc. Etc.
There is always a system / setup that will run slower than you thought possible.
Then you do not specify the speed in pixels, but in pixels per second. Each frame of animation takes a certain amount of time, etc. In your game engine, when calculating the next frame, one of your inputs is "how much time has passed since the last frame". You define this value as a fraction of a second and multiply your speed / sec by this fraction. The result is how far this value has moved since the last frame.
Please note that really slow frame rates can be detrimental to collision detection, especially with fast-moving objects. If Thing 1 goes all the way through Thing 2 between frames, just checking BBoxes or radii is not going to cut it.
Having said all this, sleep () is your friend. At the beginning of frame processing, call System.currentTimeMilis() . At the end of frame processing (including rendering), check the current time again. If the difference is not long enough, sleep (N) will be enough time to match the desired frame rate.
So, if you want a maximum of 20 frames per second, each frame should take 50 ms (1000 ms / 20 = 50 ms). If it took only 10 ms to simulate and render a frame, you need to sleep for another (50 ms - 10 ms =) 40 ms before moving on to the next frame.
Alternatively, you can run the simulation as quickly as possible, and so often display the screen. This will not help significantly increase battery life (although OpenGL hardware acceleration is expensive if there is any indication that the heat coming out of my Evo), but it can do a Very Smooth experience for it. Hell, you can start computing things like motion blur at that point.