Self-adaptive memetic algorithms for multi-objective single machine learning-effect scheduling problems with release times

This paper proposes a single machine scheduling problem with learning-effect and release times by considering two objectives requiring minimization of makespan and total tardiness, simultaneously. Due to the NP-hardness of this problem, two memetic algorithms with meme variants are presented for solving the bi-objective problem and applied by combining three different scalarization methods, including weighted sum, conic, and tchebycheff. The performance of all memetic algorithms with the meme is investigated across randomly generated twenty-seven test problems ranging from 'small' to 'large' size. The experimental results indicate that the Multimeme Memetic Algorithm using the tchebycheff outperforms the other algorithms producing the best-known results for almost all bi-objective single machine scheduling instances with learning-effects. All algorithms perform effectively in solving large-sized problems with up to 200 jobs.

Automated summary

This paper investigates a single machine scheduling problem with learning-effect and release times, and proposes two memetic algorithms for solving this problem, with experimental results showing the Multimeme Memetic Algorithm using tchebycheff outperforming other algorithms. These algorithms are effective in solving large-sized problems with up to 200 jobs.