We present Scheduling Modulo Equality (SME), the first joint approach to instruction scheduling and algebraic rewriting with e-graphs. SME uses standard equality saturation for algebraic rewriting, but a novel integer-linear programming formulation of instruction scheduling for e-graph extraction. We apply SME to polynomial evaluation and prefix sum on CPU and GPU and show that it is able to find instruction schedules that achieve up to a 2.15× speedup over optimized baselines.