The occurrence of setup times for the preparation of machines is a natural assumption when considering scheduling problems. They may occur, for example, as startup times for machines or for the (re-)configuration of machines between the processing of jobs of different types. In this thesis, we study two kinds of models for scheduling problems incorporating such setup times. The first kind of model considers jobs that are partitioned into several classes. Whenever a machine switches between the processing of jobs of different classes, a setup for the reconfiguration of the machine needs to take place. We study this problem for parallel machines with the objective of minimizing the makespan. We design and analyze approximation algorithms for the case of identical and heterogeneous machines. Additionally, we generalize the problem by allowing jobs to arrive over time and by considering the minimization of the maximum flow time. We give an approximation algorithm for the offline case of a single machine and study the (smoothed) competitiveness of a simple online algorithm. The second model deals with jobs that need to be processed on machines rented from the cloud and the minimization of the rental cost. We consider the availability of two heterogeneous types of machines that can be rented for arbitrary durations but incur a setup time for booting newly rented machines. We develop and analyze an online algorithm for jobs with deadlines arriving over time.