In this paper, our contributions are two-fold: First, we enhance the Min-Min and Sufferage heuristics under three risk modes driven by security concerns. Second, we propose a new Space-Time Genetic Algorithm (STGA) for trusted job scheduling, which is very fast and easy to implement. Under our new model, a job can possibly fail if the site security level is lower than the job security demand. We consider three security-driven heuristic modes: secure, risky, and f-risky. The secure mode always dispatches jobs to secure sites meeting the job security demands. The risky mode allocates jobs to any available resource site, taking whatever the risk it may face. The f-risky mode tries to limit the risk to be at most certain probability f. Our extensive simulation results indicated that the proposed STGA is highly effective in scheduling two types of practical workloads: NAS (Numerical Aerodynamic Simulation) and PSA (parametersweep application). The STGA outperforms the Min-Min and Sufferage heuristics under three risk modes, in terms of a wide range of performance metrics including makespan, average response time, site utilization, slowdown ratio, and job failure rate.