Scheduling is a very wide topic in combinatorial optimization with applications ranging from production and manufacturing systems to transportation and logistics systems. Stated generally, the objective of scheduling is to allocate optimally scarce resources to activities over time. More specifically, given a set of jobs and a set of machines, scheduling optimization problems look for schedules s of the jobs on the machines that satisfy the side constraints and minimize the objective function f(s). We focus in this project on scheduling problems for which a schedule is completely characterized by the order in which the tasks are processed on the machines. For instance, we do not allow insertion of idle time between the processing of consecutive tasks. Various sources of uncertainty affect real scheduling problems, among which machine breakdowns, working environment changes, worker performance instabilities, tool quality variations and unavailability. Ignoring these uncertainties usually yields schedules that perform poorly under real conditions. Hence, researchers have introduced frameworks where the uncertainty is directly taken into account, either by considering random variables as input or in a worst-case approach where the uncertainty parameters are constrained in a set. These frameworks are respectively denoted by Stochastic Programming and Robust Optimization (RO). We disregard the former in this project because of its requirement for a probabilistic distribution of the random inputs, which is very difficult to obtain in practice. We focus instead on Robust Scheduling, which can be defined as follows. We are given uncertainty set U and we look for a schedule s that minimizes the objective function under the most adverse circumstance represented by U. Robust schedules are desirable from a practical perspective because they hedge against adverse conditions of the system. In spite of its practical relevance, robust scheduling has hardly become a practical tool since very simple scheduling problems become NP-hard as soon as U contains more than one scenario. This result is however not surprising because it is known that robust combinatorial optimization problems are, more often that not, harder than their deterministic counterpart. In this context, the positive results of Bertsimas and Sim (2003) opened a new avenue of research in robust combinatorial optimization. They introduced a new type of uncertainty set, denoted budgeted uncertainty, which keeps the complexity and approximability properties of the deterministic counterparts for robust combinatorial optimization that have a linear objective function and uncertain cost coefficients. Despite its practical relevance and its desirable computational properties, the budgeted uncertainty set has not yet been used in the robust scheduling literature. Our objective in this project is to start filling this gap: we will investigate combinatorial algorithms and integer programming formulations for robust scheduling problems with processing time uncertainty assuming that the processing times belong to that set. We expect that the resulting algorithms can turn budgeted robust scheduling into an efficient tool to handle processing time uncertainty.