Structure of a simple scheduling polyhedron

In a one-machine nonpreemptive scheduling problem, the feasible schedules may be defined by the vector of the corresponding job completion times. For given positive processing times, the associated simple scheduling polyhedron P is the convex hull of these feasible completion time vectors. The main result of this paper is a complete description of the minimal linear system defining P. The paper also gives a complete, combinatorial description of the face lattice of P, and a simple, O(nlogn) separation algorithm. This algorithm has potential usefulness in cutting plane type algorithms for more difficult scheduling problems.