This paper presents a novel methodology using parametric programming techniques to solve scheduling problems under uncertainty. The uncertainty present in processing times and equipment availabilities is incorporated into scheduling models, which are then transformed to multiparametric mixed-integer linear programming (mp-MILP) problems. A solution procedure that is based on recently proposed state-of-the-art mp-MILP algorithms is then discussed. A key advantage of the proposed methodology is that the complete map of optimal schedules can be obtained as a function of various parameters; rescheduling can thus be performed via simple function evaluations without any further optimization. Therefore, the proposed methodology contributes to the construction of a proactive scheduling system. Numerical examples are presented to illustrate the potential of the proposed methodology.