Mixed-integer linear programming (MILP) methods for integration of production planning and scheduling

This thesis deals with development of modeling approaches and solutions strategies for integration of production planning and scheduling. Production planning is meant to make coarse decisions over a medium-term horizon, while scheduling is meant to model fine decisions over a short-term horizon. Usually, a production planning problem is solved to first establish facility-wide decisions (such as production targets), then scheduling models are solved to implement such decisions. A major concern with any sequential approach is that the initial production planning optimization inadequately takes into account scheduling-level information. Since production planning and scheduling can both be formulated as mixed-integer linear programming (MILP) models, it is possible that they be combined into a single "integrated" MILP model. However, this results in a medium-term scheduling problem that is computationally intractable upon being passed to a commercial MILP solver.;This thesis begins with a review of production planning models, scheduling models, and modeling approaches and solution strategies for solving the integrated model.;Recognizing that scheduling contributes by making "scheduling-level" information available, production planning models are complicated to incorporate such information. The traditional Lot-Sizing Problem (LSP) model for production planning is extended so that setups are no longer affected by time period boundaries: (1) setups already finished in a period may carry over into the next period, allowing continued production without redundant setup; (2) setups may start and finish in different periods, even a much later period; and (3) number of setups per period is not limited.;The LSP model is separately extended to correctly model two-items-two-stage continuous production in the presence of intraperiod production lead-time, item/unit-specific setup, item/unit-specific production rate, and initial inventory of intermediate inventory. Two MILP models are developed to provide numerically superior solutions.;In the opposite research direction, scheduling models are simplified. An algorithm is developed for approximating the convex hull of any (scheduling) model's projection onto any subset of its variables (e.g. onto attainable production targets). A second algorithm is developed for exploring this generated approximation to identify and iteratively remove infeasibility. The first algorithm produces an LP surrogate mode; the second algorithm produces a MILP surrogate model.