Real-life scheduling problems often require computing solutions on-line, due to real-time requirements. In this scenario, greedy algorithms guided by priority rules are of common use. This is the case of the problem of scheduling jobs on a machine with variable capacity and total tardiness minimization, denoted (1, Cap(t)‖ΣT_i). Recent work proposed a Genetic Programming (GP) approach for evolving priority rules for this problem, outperforming several well-known classical rules. In this paper, we consider state space search as an alternative framework and propose a new method based on a refined exhaustive enumeration of priority rules. Our approach, termed Systematic Search and Heuristic Evaluation (SSHE), integrates powerful pruning techniques and an efficient heuristic procedure used to evaluate candidate rules. Experimental results indicate that SSHE represents a valuable alternative to GP.