Polyhedral combinatorics is the systematic study of finite convex sets, expressed through linear inequalities. It represents one of the more promising approaches to attack problems in combinatorial optimization. A large number of computationally hard problems can be expressed easily as integer programs. However, integer programs are not easy to solve, either theoretically or practically. But the relaxations of integer programs to linear programs or semi-definite programs are polynomial time solvable. These relaxations, while not optimal, yield useful information about the problem at hand in the form of lower bounds, which in turn could provide strategies for the design of approximation algorithms. My research is concerned with determining the complexity of certain polyhedral problems as they relate to scheduling.