| A classical method for solving hard combinatorial problems is based on formulating these problems as set-partitioning models. The efficiency of the method relies upon the quality of the lower bound provided by the linear relaxation of the set-partitioning formulation. In this thesis, we apply a set-partitioning approach to machine scheduling and supply-chain management problems and analyze the linear programming relaxations of the resulting formulations in order to characterize and exploit their effectiveness.;First, we consider a class of parallel machine scheduling problems and their associated set-partitioning formulations. We show that the effectiveness of the linear programming relaxation of these formulations is directly related to the performance of a class of heuristics called parameter list scheduling heuristics. This enables us to characterize the worst possible gap between optimal solutions for the scheduling problems and the corresponding linear programming relaxations. In particular, we show that the relative gap is no more than ;For the WCTP, we consider the time-discretized formulation and study the effectiveness of its linear programming relaxation. This formulation is closely related to set-partitioning and is, thus, amenable to a similar analysis. Consequently, the results mentioned above hold for the time-discretized formulation as well.;Finally, we study the problem of integrating inventory policies and transportation strategies in the supply chain. The focus is on problems faced by companies that rely on third parties, such as LTL (Less-Than-Truck-Load) carriers, for the distribution of products. In this case, the timing and routing of shipments need to be coordinated to minimize total system costs, including inventory, routing and shortage costs, by taking advantage of economies of scale. We model this problem using a set-partitioning approach and study structural properties of the resulting formulation. This analysis enables us to characterize cases in which the linear programming relaxation is tight and to develop an effective algorithm. |
