A multi-point simulated annealing heuristic for solving multiple objective unrelated parallel machine scheduling problems

Abstract

This study considers the problem of job scheduling on unrelated parallel machines. A multi-objective multi-point simulated annealing (MOMSA) algorithm was proposed for solving this problem by simultaneously minimising makespan, total weighted completion time and total weighted tardiness. To assess the performance of the proposed heuristic and compare it with that of several benchmark heuristics, the obtained sets of non-dominated solutions were assessed using four multi-objective performance indicators. The computational results demonstrated that the proposed heuristic markedly outperformed the benchmark heuristics in terms of the four performance indicators. The proposed MOMSA algorithm can provide a new benchmark for future research related to the unrelated parallel machine scheduling problem addressed in this study.

Keywords:

• scheduling
• parallel machine
• multi-objective
• multi-point
• simulated annealing

Acknowledgment

The author would like to thank Prof. Yang-Kuei Lin for making his benchmark problem set and solutions to us.

Additional information

Funding

Funding. This research was partially supported by the National Science Council of the Republic of China (Taiwan) grants NSC 102-2221-E-027-056 and NSC 101-2410-H-182-004-MY2.