Dinkelbach's algorithm as an efficient method to solve a class of MINLP models for large-scale cyclic scheduling problems

Fengqi You, Pedro M. Castro, Ignacio E. Grossmann*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

79 Scopus citations

Abstract

In this paper we consider the solution methods for mixed-integer linear fractional programming (MILFP) models, which arise in cyclic process scheduling problems. We first discuss convexity properties of MILFP problems, and then investigate the capability of solving MILFP problems with MINLP methods. Dinkelbach's algorithm is introduced as an efficient method for solving large-scale MILFP problems for which its optimality and convergence properties are established. Extensive computational examples are presented to compare Dinkelbach's algorithm with various MINLP methods. To illustrate the applications of this algorithm, we consider industrial cyclic scheduling problems for a reaction-separation network and a tissue paper mill with byproduct recycling. These problems are formulated as MILFP models based on the continuous time Resource-Task Network (RTN). The results show that orders of magnitude reduction in CPU times can be achieved when using this algorithm compared to solving the problems with commercial MINLP solvers.

Original languageEnglish (US)
Pages (from-to)1879-1889
Number of pages11
JournalComputers and Chemical Engineering
Volume33
Issue number11
DOIs
StatePublished - Nov 12 2009

Keywords

  • Cyclic scheduling
  • Dinkelbach's algorithm
  • Mixed-integer linear fractional programming
  • Resource-Task Network

ASJC Scopus subject areas

  • Chemical Engineering(all)
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Dinkelbach's algorithm as an efficient method to solve a class of MINLP models for large-scale cyclic scheduling problems'. Together they form a unique fingerprint.

Cite this