A comparison of algorithms for minimizing the sum of earliness and tardiness in hybrid flow-shop scheduling problem with unrelated parallel machines and sequence-dependent setup times

Abstract

In this paper, the flow-shop scheduling problem with unrelated parallel machines at each stage as well as sequence-dependent setup times under minimization of the sum of earliness and tardiness are studied. The processing times, setup times and due-dates are known in advance. To solve the problem, we introduce a hybrid memetic algorithm as well as a particle swarm optimization algorithm combined with genetic operators. Also, an application of simulated annealing is presented for the evaluation of the algorithms. A Taguchi design is conducted to set their parameters. Finally, a comparison is made via 16 small size and 24 large size test problems and each problem is run 10times. The results of one-way ANOVA demonstrate that the proposed memetic algorithm performs as efficient as the HSA qualitatively and with 63.77% decline in elapsed time.