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. We also give a complete, combinatorial description of the face lattice of P, and a simple, O(n log n) separation algorithm. This algorithm has potential usefulness in cutting plane type algorithms for more difficult scheduling problems.