Optimization techniques for production planning and scheduling of co-product networks

This dissertation introduces a computationally attractive algorithm that generates efficient and feasible solutions for a special class of network problems, known as processing networks, in which some arcs have predetermined flows (fixed split) once a predecessor arc flow is given.; This type of network is quite prevalent in many different types of manufacturing systems. Illustrative examples drawn from semiconductor manufacturing are used to make comparisons between several solution techniques including linear programming, material requirements planning (the standard industrial methodology), and our algorithm.; These examples show that for this problem in its most general form only linear programming is able to generate a solution that is both efficient, in terms of discounted cash flow, and feasible. Our algorithm is able to generate a feasible solution in all cases, but it will not be efficient in the most general case (production requirements can be calculated but can not be efficiently scheduled). Fortunately this is not too much of a drawback since it has been estimated that approximately 80% of the problems typically encountered in semiconductor manufacturing are what are known in the industry as straight downbinning problems. Additionally, there are problems not strictly classified as straight downbinning problems that may be handled by a slight modification of our algorithm.; Under these conditions our algorithm computes feasible production schedules that are optimal in the sense that the total production quantity required is minimized and that production in any time period may not be delayed to the next time period and still maintain feasibility unless production in an earlier time period is increased. Further, our algorithm is computationally much faster than a linear programming solution utilizing the Simplex algorithm or an interior point algorithm.