We present a novel pre-runtime scheduling method for uni-processors which precisely incorporates the effects of task switching on the processor cache into its decisions. Tasks are modelled as a sequence of non preemtable segments with precedence constraints. The cache behavior of each task segment is statically determined by interpretation. For the sake of efficiency, the scheduling algorithm uses a heuristically guided search strategy. Each time a new task segment is added to a partial schedule, its worst case execution time is calculated based on the cache state at the end of the preceding partial schedule.