An effective benders decomposition algorithm for solving the distributed permutation flowshop scheduling problem

Abstract In today's centralized globalized economy, large manufacturing firms operate more than one production center. Therefore, the multifactory production scheduling environment, so-called the distributed scheduling problem, is gaining more and more attention from the authors. In this context, which factory will manufacture which product is an important decision making process. The distributed permutation flowshop scheduling problem (DPFSP) provided with real life applications has attracted attention of the researchers for nearly one decade as one of the special cases of the distributed scheduling problem. In the current literature, approximation methods have been intensely used for solving the DPFSP and only one paper containing the exact solution methods has been published to solve this problem. In this paper, the best mathematical formulations available in the current literature has been further improved and traditional and hybrid Benders decomposition algorithms are presented through the proposed new mathematical model. The developed new model is a position based model intended for restricting the domains of decision variables and assigning jobs to sequential positions in the related decision variables. The proposed hybrid Benders decomposition algorithm consists of the hybridization of NEH2_en local search algorithm, a mathematical model to find the upper bound for the number of positions used in the related decision variables, the LS3 algorithm, with the Benders decomposition algorithms. The new and best exact methods available in the literature are compared with each other by using the benchmark data sets and the experimental results showed that the new exact methods developed in this paper are superior to the existing exact methods in all aspects. In this paper, 18 new best solutions are founded for the DPFSP.