In a large embedded real-time system, priority assignment can greatly affect the timing behavior--which can consequently affect the overall behavior--of the system. Thus, it is crucial for model-based design of a large embedded real-time system to be able to intelligently assign priorities such that tasks can meet their deadlines. In this paper, we propose a priority refinement method for dependent tasks distributed throughout a heterogeneous multiprocessor environment. In this method, we refine an initial priority assignment iteratively using the simulated annealing technique with tasks’ latest completion times (LCT). Our evaluations, based on randomly-generated models, have shown that the refinement method outperforms other priority assignment schemes and scales well for large, complex, real-time systems. This method has been implemented in the Automatic Integration of Reusable Embedded Software (AIRES) toolkit and has been successfully applied to a real vehicle system control application.