In this paper, we consider single machine scheduling problems with given release dates and the objective to minimize the maximum penalty which is NP-hard in the strong sense. For this problem, we introduce a dual and an inverse problem and show that both these problems can be solved in polynomial time. Since the dual problem gives a lower bound on the optimal objective function value of the original problem, we incorpo- rate the optimal function value of a sub-problem of the dual problem into a branch and bound algorithm for the original single machine scheduling problem. We present some initial computational results for instances with up to 20 jobs.