An evolutionary algorithm with path-relinking for the parallel machine with job splitting

This paper addresses the parallel machine scheduling problem which consists in the assignment of n jobs on m identical machines with the objective of minimizing the total tardiness of the jobs using the job splitting property. In this problem is assumed that a job can be split into sub-jobs and these sub-jobs can be processed independently on parallel machines. This is an NP-hard problem and few solution methods have been proposed to solve it. In this paper, we propose a Genetic Algorithm coupled with Path Relinking intensification to obtain near-optimal solutions of the problem. To evaluate the performance of the algorithm, computational experiments are performed on a benchmark of small and large instances of the problem. Results of the experiments show that the proposed algorithm outperforms others algorithms previously proposed in the literature in terms of solution quality. The results are confirmed by a statistical analysis.