This paper deals with the polyhedral structure of the scheduling problem R//Cmax. Strong valid inequalities are identified for fixed values of the maximum completion time and are used to build a cutting plane scheme from which an exact algorithm and an approximation algorithm are developed. The main algorithm includes a preprocessing phase to compute an upper bound with the list scheduling algorithm of Davis and Jaffe and a lower bound from the preemptive version of the problem. Computational results show that the proposed exact algorithm gives an optimal solution for almost all tested cases, within the fixed time and memory limits. For the few cases where the limit has been exceeded, rather good solutions are obtained. Computational requirements of both algorithms are reported for a collection of test problems and the quality of the schedules provided by the approximation algorithm is measured.
