Engineered algorithms for optimization problems with application to scheduling and control

This thesis presents engineered algorithms for a class of scheduling and process control problems. The problem in process scheduling belongs to the class of constrained cutting stock problems. A novel algorithm, very effective in solving industrial scale problems and a software implementation robust enough for routine day to day use have been developed. This algorithm is at the core of a scheduling system which assigns inventory to orders, generates restock orders, computes a sequence of slitter web patterns and schedules the patterns for production. The performance of the system, which has been in operation for over two years, has been excellent. A rigorous mathematical programming model for this problem has also been developed. In the second part of this work, a linear programming based model predictive control strategy for solving linear process control problems is presented. This strategy is applied to the paper machine cross direction (CD) control problem. The objective of CD control is to maintain flat profiles of variables of interest by minimizing worst case deviations from setpoints (defects). These control problems can have as many as 400 actuators (inputs) and 400 sensor measurements (outputs). This large size coupled with the stringent real-time requirement of computing a control move in a few seconds poses a very challenging control problem. The LP based strategy is particularly well suited for solving such classes of control problems. It has demonstrated ability to solve large scale control problems in real time and exhibits robustness to model uncertainty. Although, a generic LP implementation performed adequately for problems of size up to 119 x 119, it was not fast enough for problems of larger dimensions. In order to address this limitation, a tailored LP algorithm that effectively solves problems larger in scale was devised. The customized algorithm can compute provably optimal control moves for typical 400 input x 400 output control problems in approximately 5 seconds versus approximately 90 seconds for a generic LP algorithm on a HP 9000/770 workstation