Trusted Computing is a technology proposed by the Trusted Computing Group (TCG) to solve security problems in computers. A lot of work has been conducted to support Trusted Computing for individual computers; however little has been done for distributed systems (e.g., clusters). If malicious or unqualified applications are deployed on cluster nodes, users may obtain forged results or their data may be leaked out. In this paper, a methodology of the Trusted Cluster Computing (TCC) is proposed to automatically construct user-trustable cluster computing environments. User-specified applications are downloaded from user-specified locations and automatically and dynamically deployed on cluster nodes. To reduce the dynamic-deployment overhead, a novel Heuristics-based Overhead-Reducing (HOR) replacement strategy is also proposed. A highly configurable simulator has been implemented to perform a series of simulations. The simulation results demonstrate that the HOR can produce Average Speedup with up to 14% (light workload), 10% (medium workload), 8% (heavy workload) higher than that of LRU-based strategies, with a typical setting of the Average Ratio of Deployment time to Execution time (ARDE) being 0.2.