Pareto-based Multicriteria Evolutionary Algorithm for Parallel Machines Scheduling Problem with Sequence-dependent Setup Times

This paper addresses an unrelated multimachine scheduling problem with sequencedependent setup time, release date and processing set restriction to minimize the sum of weighted earliness/tardiness penalties and the sum of completion times, which is known to be NPhard. A Mixed Integer Programming (MIP) model is proposed to formulate the considered multicriteria problem. Also, to solve the model for realsized applications, a Paretobased algorithm, namely controlled elitism nondominated sorting genetic algorithm (CENSGA), is proposed. To validate its performance, the algorithm is examined under six performance metric measures, and compared with a Paretobased algorithm, namely NSGAII. The results are statistically evaluated by the Mann–Whitney test and ttest methods. From the obtained results based on the ttest, the proposed CENSGA significantly outperforms the NSGAII in four out of six terms. Additionally, the statistical results from Mann–Whitney test show that the performance of the proposed CENSGA is better than the NSGA II in two out of six terms. Finally, the experimental results indicate the effectiveness of the proposed algorithm for different problems.