Abstract:

The distributed permutation flowshop scheduling problem (DPFSP) is a generalization of the regular flowshop scheduling problem where several factories are accessible for processing the jobs. In this paper, two new mathematical models are developed by deriving inspiration from the formulations developed for the multiple-traveling salesman problem (mTSP), and six different pure Benders decomposition algorithms are developed based on different mathematical model formulations. In addition, a hybrid Benders decomposition algorithm is developed through the best performed mathematical. Nine newly developed exact methods are compared in detail with each other, the best mathematical models given by Naderi and Ruiz (2010) and an automatic Benders decomposition algorithm by using the 84 problem instances available in the literature. The consequences of the experiment performed for the comparison of all existing and new exact algorithms have revealed that the proposed hybrid Benders decomposition algorithm has outperformed considerably when compared to the other methods. In this paper, 4 new best solutions are identified for the DPFSP.

Keywords: