LOGIC-BASED OPTIMIZATION MODELS AND ALGORITHMS FOR ADVANCED PLANNING AND SCHEDULING

by

Metin Turkay
Koc Unıversity


Advanced planning and scheduling integrates medium term planning activities with detailed implementation plans in the production systems. During the last two decades modeling and optimization has been a focal research subject in advanced planning and scheduling. An important bottleneck in the development of accurate and efficient models and solution algorithms is the integration of the discrete nature of these problems into models and also exploitation of the interdependencies among discrete decisions during the solution of the resulting optimization problems.

Generalized Disjunctive Programming (GDP) is used as the modeling framework in the supply chain management problems to overcome difficulties with traditional equation-based modeling approaches for discrete-continuous systems. The GDP is a natural modeling framework in which discrete decisions and discrete behaviors of systems are represented. The discrete nature of systems is represented using disjunctions and each disjunction includes constraints and a cost function that is applicable only when the disjunction is true. In addition the interdependencies among discrete decisions are expressed using propositional logic. The propositional logic can be applied in two ways: by obtaining equivalent algebraic constraints and adding these constraints to the set of original constraints or by using the propositional logic through an inference engine in the branch and bound algorithm. The first approach improves the relaxation gap of the mixed-integer programming problems while the second approach allows fixing additional binary variables at each node of the branch and bound tree that result in substantial improvements in the solution of certain classes of mixed-integer programming problems.

The proposed approach for solving mixed-integer programming problems and application to advanced planning and scheduling will be illustrated.