| In this thesis, three mathematical models in the areas of machine scheduling and inventory control are studied. The first model considers due date assignment and scheduling on parallel machines. Two approximation algorithms are developed to solve two different cases of the problem. Worst case analysis is performed, and a fully polynomial approximation scheme is developed as well. The second model is a multi-product dynamic lot size model with one-way product substitution. Two sub-models are provided for two types of product substitution, namely substitution with conversion and substitution without conversion. These sub-models are proven to be computationally intractable. Dynamic programming algorithms are developed to solve these problems. Our algorithms have a polynomial running time when the number of products is fixed. While the first and second models focus on scheduling and inventory issues independently, the third model considers the coordination of machine schedules and inventory plans between a manufacturer and a supplier through the use of a lot streaming model. Methods for obtaining the optimal solution in both the centralized and decentralized systems are developed. Coordination mechanisms are developed to entice each of the two parties to make the systemwide optimal decision. The robustness issue of this model is also addressed. |
