We address problems associated with testing real-time systems with on-line scheduling where no exact estimations of worst-case execution times or load patterns can be acquired. Under these circumstances, testing the timeliness of a real-time system is imperative for gaining confidence in its correctness. In such real-time systems a huge e®ort is associated with testing due to nondeterminism of the execution environment. A framework for testing is proposed, which include an approach for test case generation, testing criteria for timeliness testing, and methods for automating the test-case execution process. The suggested framework uses a formalized model for specifying the execution environment and applications so that relevant execution orders of tasks can be selected. Test data is then produced for demonstrating that critical execution orders do not cause timing constraints to be violated.