A novel chemical reaction optimization for the distributed permutation flowshop scheduling problem with makespan criterion

The Permutation Flowshop Scheduling Problem (PFSP) is among the most investigated scheduling problems in the fields of Operational Research (OR) and management science. During the last six decades, it has gained much attention and interest thanks to its applicability in a variety of domains such as industrial engineering and economics. Recently, the PFSP with multi-factory environment has been proposed in shop scheduling sphere. Since the problem is known to be NP-hard, exact algorithms can be extremely costly, computationally speaking. Chemical Reaction Optimization (CRO) is lastly proposed by Lam and Li (2010) to optimize hard combinatorial problems. Due to its ability to escape from local optima, CRO has demonstrated excellent performance in solving a variety of scheduling problems, such as flexible job-shop scheduling, grid scheduling, network scheduling etc. In such a paper, we address the Distributed Permutation Flowshop Scheduling Problem (DPFSP) with an artificial chemical reaction metaheuristic which objective is to minimize the maximum completion time. In the proposed CRO, the effective NEH heuristic is adapted to generate the initial population of molecules. Furthermore, a well-designed One-Point (OP) crossover and an effective greedy strategy are embedded in the CRO algorithm in order to ameliorate the solution quality. Moreover, the influence of the parameter setting on the CRO algorithm is being investigated on the base of the Taguchi method. To validate the performance of the proposed algorithm, intensive experiments are carried out on 720 large instances which are extended from the well known Taillard benchmark. The results prove the efficiency of the proposed algorithm in comparison with some powerful algorithms. It is also seen that more than 200 best-known solutions are improved.