In this paper we have identified three sub-problems re- lated to the optimal priority assignment for real-time sys- tems with probabilistic execution times when scheduled preemptively on one processor according to fixed prior- ities. For each sub-problem we propose an algorithm that is proved optimal. The first two algorithms are inspired from an existing priority assignment known as Audsley's algorithm which is a greedy (lowest priority first) algo- rithm. Since we prove that such greedy algorithm is not suitable for the third problem, we propose a tree search algorithm in this case.