Decomposition techniques for multistage scheduling problems using mixed-integer and constraint programming methods

Research output: Contribution to journalArticle


Research units

  • Carnegie Mellon University


In this paper two strategies are presented to reduce the combinatorial complexity when solving single stage and multistage optimization scheduling problems that involve cost minimization and due dates. These problems can naturally be decomposed into assignment and sequencing subproblems. The proposed strategies rely on either combining mixed-integer programming (MILP) to model the assignment part and constraint programming (CP) for modeling the sequencing part, or else combining MILP models for both parts. The subproblems are solved sequentially by adding integer cuts to the first MILP to generate new assignments. Results are presented for both single and multistage systems.


Original languageEnglish
Pages (from-to)1533-1552
Number of pages20
JournalComputers and Chemical Engineering
Issue number11
Publication statusPublished - 15 Nov 2002
MoE publication typeA1 Journal article-refereed

    Research areas

  • Constraint programming, Hybrid strategy, Mixed integer programming, Multistage scheduling

ID: 6322753