Dinkelbach’s Algorithm as an Efficient Method for Solving a Class of MINLP Models for Large-Scale Cyclic Scheduling Problems

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 a 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.