In this paper, we consider scheduling problems on a single machine in a sequence dependent setup environment. We introduce for these problems several integer programming formulations of various size and various strength. Computational experiments conducted on instances of (i.e. minimizing the total flow time on a single machine under sequence dependent setup times) and (i.e. minimizing the total tardiness on a single machine under sequence dependent setup times) illustrate the benefits of using stronger formulations, even though the computation of their LP relaxation is more time consuming. Incorporating these improved LP relaxation bounds, we propose an exact branch-and-bound algorithm able to solve instances of and having up to 50 and 45 jobs respectively.