An evolution strategy approach for the distributed permutation flowshop scheduling problem with sequence-dependent setup times

Abstract

This paper considers a distributed permutation flowshop scheduling problem with sequence-dependent setup times (DPFSP-SDST) to minimize the maximum completion time among the factories. The global economy has enabled large companies to have distributed production centers to become widespread and effective production scheduling between these centers plays a vital role in the competitiveness of companies. To provide effective scheduling for the DPFSP-SDST we propose a new mixed-integer linear programming (MILP) model and a new constraint programming (CP) model which is presented for the first time in literature to the best of our knowledge. As the CP has become a solid competitor to the MILP in the literature this study aims to exploit the effectiveness of CP to solve such a complex DPFSP-SDST. Since the problem is NP-hard we also offer an evolution strategy (ES_en) algorithm that employs a self-adaptive scheme to obtain high-quality solutions in a short time. A ruin-and-recreate procedure is also embedded into the developed ES_en. We calibrate the parameters of the proposed ES_en using a design of experiment approach. We also compare the proposed ES_en algorithm's performance with three state-of-the-art metaheuristic algorithms from the literature i.e. the IG2S (a variant of an iterated greedy algorithm with NEH2_en initialization) IGR (another variant of an iterated greedy algorithm with a restart scheme) and discrete artificial bee colony (DABC) algorithm. A detailed computational experiment is carried out to evaluate the performance of the mathematical models (MILP and CP) and the heuristic algorithms (ES_en IG2S IGR and DABC). A comprehensive benchmark set is generated for the DPFSP-SDST from the well-known PFSP instances from the literature considering various combinations of jobs machines factories and SDST settings resulting in 2880 benchmark instances. For 216 out of 240 small-size instances optimal results are reported by solving the proposed MILP and CP models whereas time-limited model results are reported for the rest. The computational results show that the CP model outperforms the MILP model in terms of the solution time for small-size instances. Initially the performance of the heuristic algorithms is verified concerning the optimal results on small-size instances. Then the performance of the heuristic algorithms is evaluated for large instances. ES_en algorithm significantly outperforms the IG2S IGR and DABC algorithms for solving large instances. The computational results show that the proposed ES_en algorithm is robust and provides good-quality solutions for the DPFSP-SDST in a short computational time.