We study the single machine version of the task scheduling problem with release times and deadlines. This problem is too simple to be of practical importance in itself, but it is also used as a relaxation in algorithms for the Job Shop scheduling problem, which is a more practical task scheduling problem. We study exact algorithms for solving the single machine problem. We propose a new lower bound for the single machine problem and analyze its practical performance when used in a branch and bound algorithm. We also study the theoretical hardness of the single machine problem with a fixed set of task lengths.