Structure of a simple scheduling polyhedron (Q1803611)

Properties of a simple scheduling polyhedron \(P\) for one-machine nonpreemptive scheduling problem are considered. Any feasible schedule in one-machine nonpreemptive scheduling problem is defined by the vector of job completion times. The polyhedron \(P\) is the convex hull of all feasible completion time vectors. A complete description of \(P\) by a minimal system of linear inequalities is suggested. The author gives also a complete combinatorial description of the face lattice of \(P\) and proposes an \(O(n \log n)\) separation algorithm, which may be used for constructing cutting plane type algorithms for solving different scheduling problems.