An evolutionary variable neighbourhood search for the unrelated parallel machine scheduling problem

Abdullah, Salwani ORCID: 0000-0003-0037-841X, Turky, Ayad ORCID: 0000-0001-8415-7328, Ahmad Nazri, Mohd Zakree ORCID: 0000-0003-2267-4965 and Sabar, NR ORCID: 0000-0002-0276-4704 (2021) An evolutionary variable neighbourhood search for the unrelated parallel machine scheduling problem. IEEE Access, 9. pp. 42857-42867. ISSN 2169-3536


This article addresses a challenging industrial problem known as the unrelated parallel machine scheduling problem (UPMSP) with sequence-dependent setup times. In UPMSP, we have a set of machines and a group of jobs. The goal is to find the optimal way to schedule jobs for execution by one of the several available machines. UPMSP has been classified as an NP-hard optimisation problem and, thus, cannot be solved by exact methods. Meta-heuristic algorithms are commonly used to find sub-optimal solutions. However, large-scale UPMSP instances pose a significant challenge to meta-heuristic algorithms. To effectively solve a large-scale UPMSP, this article introduces a two-stage evolutionary variable neighbourhood search (EVNS) methodology. The proposed EVNS integrates a variable neighbourhood search algorithm and an evolutionary descent framework in an adaptive manner. The proposed evolutionary framework is employed in the first stage. It uses a mix of crossover and mutation operators to generate diverse solutions. In the second stage, we propose an adaptive variable neighbourhood search to exploit the area around the solutions generated in the first stage. A dynamic strategy is developed to determine the switching time between these two stages. To guide the search towards promising areas, a diversity-based fitness function is proposed to explore different locations in the search landscape. We demonstrate the competitiveness of the proposed EVNS by presenting the computational results and comparisons on the 1640 UPMSP benchmark instances, which have been commonly used in the literature. The experiment results show that our EVNS obtains better results than the compared algorithms on several UPMSP instances.

Dimensions Badge

Altmetric Badge

Item type Article
DOI 10.1109/ACCESS.2021.3065109
Official URL
Subjects Current > FOR (2020) Classification > 4602 Artificial intelligence
Current > Division/Research > College of Science and Engineering
Keywords unrelated parallel machine scheduling problem, UPMSP, algorithms, evolutionary variable neighbourhood search, EVNS
Citations in Scopus 2 - View on Scopus
Download/View statistics View download statistics for this item

Search Google Scholar

Repository staff login