A hybrid MILP/CP decomposition approach for the continuous time scheduling of multipurpose batch plants

Christos T. Maravelias, Ignacio E. Grossmann

Research output: Contribution to journalArticlepeer-review

121 Scopus citations

Abstract

A hybrid Mixed-Integer Linear Programming (MILP)/Constraint Programming (CP) decomposition algorithm is proposed for the short-term scheduling of batch plants that rely on the State Task Network (STN) representation. The decisions about the type and number of tasks performed, as well as the assignment of units to tasks are made by the MILP master problem (MP). The CP subproblem checks the feasibility of a specific assignment and generates integer cuts for the master problem. A graph-theoretic preprocessing that determines time windows for the tasks and equipment units is also performed to enhance the performance of the algorithm. To exclude as many infeasible configurations as possible, three classes of integer cuts are generated. Various objective functions such as the minimization of assignment cost, the minimization of makespan for fixed demand and the maximization of profit for a fixed time horizon can be accommodated. Variable batch-sizes and durations, different storage policies, and resource constraints are taken into account. The proposed framework is very general and can be used for the solution of almost all batch scheduling problems. Numerical results show that for some classes of problems, the proposed algorithm can be two to three orders of magnitude faster than standalone MILP and CP models.

Original languageEnglish (US)
Pages (from-to)1921-1949
Number of pages29
JournalComputers and Chemical Engineering
Volume28
Issue number10
DOIs
StatePublished - Sep 15 2004
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Chemical Engineering(all)
  • Computer Science Applications

Keywords

  • Constraints
  • Integer cuts
  • Master problem

Fingerprint

Dive into the research topics of 'A hybrid MILP/CP decomposition approach for the continuous time scheduling of multipurpose batch plants'. Together they form a unique fingerprint.

Cite this