Over the past decade, there have been significant advances in the use of linear programming and polyhedral combinatorics for solving large-scale combinatorial optimization problems. As a result of this empirical work, there is a quite good understanding about the relative strength of various linear relaxations for a wide range of applications. We shall explore the strength of linear programming relaxations from a theoretical perspective: we are interested in designing simple heuristics with good performance guarantees that are based on first solving the relaxation. In this talk we primarily focus on applying this approach to scheduling problems, where linear relaxations have been used both to order jobs for a list-scheduling algorithm, and to assign jobs to machines. In particular, for the problem of minimizing a weighted average of the job completion times subject to precedence constraints on a single machine, there have been a number of different linear relaxations proposed, and we shall compare them from the perspective of the performance guarantee that can (and might) be proved. We will also briefly discuss some very recent work for facility location problems which relies on similar techniques. These results include joint work with Karen Aardal (Utrecht), Fabian Chudak (Cornell), Leslie Hall (Johns Hopkins), Andreas Schulz (TU-Berlin), Eva Tardos (Cornell), and Joel Wein (Polytechnic).