Resource-constrained scheduling and production planning: Linear programming-based studies

Many applications that can be modeled as systems of linear inequalities lack the divisibility property required for the straightforward application of linear programming. Nevertheless, linear programs related to these models often yield useful information that can be exploited in solution procedures. This dissertation focuses on the use of such information to construct algorithms for the allocation of scarce resources in production planning and scheduling problems. The resource-constrained scheduling problem on uniform jobs (URCSP) involves scheduling a set of jobs over a discrete time horizon, where each job requires some constant amount of a limited resource over its processing time. We introduce a class of valid inequalities for a time-formulation of URCSP in order to improve the bounds given by its linear programming relaxation, and we present results demonstrating their strength. Results obtained from the incorporation of a separation routine for this class into a branch and bound algorithm for URCSP are included. Other issues surrounding the use of branch and bound to solve instances of URCSP are addressed. We go on to study the polyhedral structure of a mixed-integer programming formulation of the dynamic knapsack problem where we are given a set of possible activities in each period over a fixed discrete time horizon. The set of activities we choose in any period may not consume more resource than is available in that period, and any unused resource is available for use in subsequent periods. We present valid inequalities for the mixed-integer programming formulation of special cases of the dynamic knapsack problem, and we show how these results may be applied to the more general problem. Finally, we study the use of linear programming solutions to drive approximation algorithms for the lot-sizing problem with zero costs on inventory and production. The problem involves determining how much of a given item to produce in each period of a fixed discrete time horizon in order to satisfy known demand. The only cost incurred is a fixed cost charged on any day that production takes place. We present several interesting results encountered in the pursuit, of a constant-factor approximation algorithm for this problem.