Greedy algorithm for scheduling batch plants with sequence-dependent changeovers

Pedro M. Castro*, Iiro Harjunkoski, Ignacio E. Grossmann

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

26 Citations (Scopus)


This article presents a new algorithm for scheduling multistage batch plants with a large number of orders and sequence-dependent changeovers. Such problems are either intractable when solved with full-space approaches or poor solutions result. We use decomposition on the entire set of orders and derive the complete schedule in several iterations, by inserting a couple of orders at a time. The key idea is to allow for partial rescheduling without altering the main decisions in terms of unit assignments and sequencing (linked to the binary variables) so that the combinatorial complexity is kept at a manageable level. The algorithm has been implemented for three alternative continuous-time mixed integer linear programing models and tested through the solution of 10 example problems for different decomposition settings. The results show that an industrial-size scheduling problem with 50 orders, 17 units distributed over six stages can effectively be solved in roughly 6 min of computational time.

Original languageEnglish
Pages (from-to)373-387
Number of pages15
JournalAIChE Journal
Issue number2
Publication statusPublished - Feb 2011
MoE publication typeA1 Journal article-refereed


  • Continuous-time
  • Mathematical modeling
  • Optimization
  • Resource-task network


Dive into the research topics of 'Greedy algorithm for scheduling batch plants with sequence-dependent changeovers'. Together they form a unique fingerprint.

Cite this