We provide a review and synthesis of polyhedral
approaches to nonpreemptive machine scheduling
problems. The choice of decision variables is the prime
determinant of various formulations for such problems.
Constraints, such as facet inducing inequalities for
corresponding polyhedra, are often needed, in addition
to those just required for the validity of the initial
formulation, in order to obtain useful lower bounds and
structural insights. We review formulations based on
time-indexed variables; on linear ordering, start time
and completion time variables; on assignment and
positional date variables; and on traveling salesman
variables. We point out relationship between various
models, and provide a number of new results, as well as
simplified new proofs of known results. In particular,
we emphasize the important role that supermodular
polyhedra and greedy algorithms play in many
formulations. We discuss separation algorithms for
several classes of inequalities, and their potential
applicability in generating cutting planes for the
practical solution of such scheduling problems.
