Mixed integer optimization models and methods for special classes of scheduling problems

This thesis deals with four different classes of industrially relevant scheduling problems. The goal is to develop efficient mixed integer optimization models and to devise new solution methods that exploit the mathematical structure of the model and utilize the practical insights about the problem. The final part of the thesis concentrates on developing optimization algorithms for a class of problems that exploit the complementary strengths of mixed integer linear programming (MILP) and constraint logic programming (CLP) optimization techniques.;An MINLP model for cyclic scheduling of multiple feeds on continuous parallel units is proposed. The performance of each unit is assumed to decrease with time, and therefore planned maintenance is required to restore its performance. The optimization tradeoff is between the performance of the units, the maintenance costs, and the loss in production due to shutdowns. The main scheduling decisions are: (a) assignment of various feeds to different units; (b) processing time of each feed on different units; (c) number of subcycles of each feed on different units.;The problem of real time scheduling of orders in the steel rolling mills and the machine shop of a steel plant is addressed. The proposed representation transforms a partially structured scheduling problem into a completely structured scheduling problem that resembles the conventional multistage problem. However, there are two major differences: firstly, an order can skip stages, and secondly, a given machine can be used in multiple stages.;A disjunctive model for the short term scheduling of a two stage continuous process with intermediate storage tanks is proposed. The model involves a disjunction for every order to select a set of units to be used to complete that order; disjunctions for all the possible pairs of orders to sequence orders on a unit; and logic propositions to relate assignment and sequencing decisions.;The problem of resource constrained scheduling of testing tasks for new product development is addressed. It is shown that it is critical to incorporate resource constraints along with sequencing of the tasks to obtain a testing schedule with minimum overall expected cost. The first MILP model relies on a slot based representation that uses parallel time coordinates to handle the resource constraints. The second MILP model is based on a graph based representation in which directed arcs are used to resolve the resource constraints. It is demonstrated with the second model that the proper combination of modeling and search strategy makes the difference in successfully tackling this problem.;Lastly, we propose a hybrid MILP/CLP model for a class of optimization problems for which only a subset of variables have non zero objective function coefficients in the MILP model. The hybrid MILP/CLP model involves some of the MILP constraints, a reduced set of CLP constraints, and equivalence relations between the MILP and the CLP variables. An MILP/CLP based decomposition method and an LP/CLP based branch and bound algorithm are proposed to solve these hybrid models. The hybrid MILP/CLP model can achieve two to three orders of magnitude reduction in CPU time. (Abstract shortened by UMI.)...