MODELING AND ANALYSIS OF A TWO-LEVEL PRODUCTION SCHEDULING PROBLEM (MANAGEMENT SCIENCE, INVENTORY SYSTEMS, OPERATIONS RESEARCH)

This dissertation discusses the generation of minimum cost and low-cost schedules for a two-level production model which uniquely combines a variety of manufacturing components. Demand for finished (level 1) products is deterministic, but time varying. The production schedule of these products creates a cascading demand for level 2 parts. A fixed number of assembly facilities is available to produce each part. The capacity, for producing a particular part, is defined by the maximum quantity that can be assembled during a single set-up, normal, or overtime period, and is assumed constant throughout the horizon. Backordering is permitted only for finished products. A sequence independent time and cost penalty is required to change over from one part to another. For each part, an initial inventory, a minimum final inventory requirement, an inventory holding charge, a shortage charge, a setup charge, and an overtime charge are specified.; The objective of this research is to analyze the structure of this problem and to develop algorithms for determining schedules, which minimize production and schedule generation costs. Necessary conditions for the existence of a feasible schedule are derived, but the problem of determining even a feasible schedule is shown to be included in the class of NP-complete problems.; A variety of optimal and heuristic solution procedures using mixed integer programming, branch and bound, dynamic programming, enumeration, and greedy techniques are described and compared, indicating conditions under which each is most appropriately applied. Problem structure is exploited to improve the solution efficiency of these algorithms. This study focuses more on the general capabilities of these various methods than on a detailed or exhaustive analysis of any particular one.; An innovative procedure, for decomposing the problem structure, is described which leads to a general methodology for analyzing, developing, and categorizing heuristic schedule generating procedures. Associated with this methodology are the issues of selecting, ordering, and sequencing fundamental problem components. A computer programming framework for evaluating schedules and subroutines corresponding to the heuristic schedule generating techniques is presented. Results obtained by applying these algorithms to several problem instances are also shown.