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.