Scheduling problems arise in a whole host of contexts, ranging from real-time systems and databases to compilers and Job-shop control. A number of these problems can be characterized through constraint systems and appropriately quantified control variables. An important feature of problem modeling is the assumption regarding the underlying data. My research is primarily concerned with the design and development of algorithms, for problems in which the assumption of constancy in input data is either restrictive or inaccurate. A typical such parameter is the execution time of a job; the assumption that a job will execute for exactly the same amount of time in every cycle is unrealistic. In an effort to address this issue, a number of error models have been developed in real-time scheduling literature. I focus on those problems in which execution time variability can be modeled through convex domains.