Hybridizing guided genetic algorithm and single-based metaheuristics to solve unrelated parallel machine scheduling problem with scarce resources

Munther H. Abed, Mohd Nizam Mohmad Kahar


This paper focuses on solving unrelated parallel machine scheduling with resource constraints (UPMR). There are j jobs, and each job needs to be processed on one of the machines aim at minimizing the makespan. Besides the dependence of the machine, the processing time of any job depends on the usage of a rare renewable resource. A certain number of those resources (Rmax) can be disseminated to jobs for the purpose of processing them at any time, and each job j needs units of resources (rjm) when processing in machine m. When more resources are assigned to a job, the job processing time minimizes. However, the number of resources available is limited, and this makes the problem difficult to solve for a good quality solution. Genetic algorithm shows promising results in solving UPMR. However, genetic algorithm suffers from premature convergence, which could hinder the resulting quality. Therefore, the work hybridizes guided genetic algorithm (GGA) with a single-based metaheuristics (SBHs) to handle the premature convergence in the genetic algorithm with the aim to escape from the local optima and improve the solution quality further. The single-based metaheuristics replaces the mutation in the genetic algorithm. The evaluation of the algorithm performance was conducted through extensive experiments.


Genetic algorithm; Great deluge; Hybridization; Makespan; Tabu search; Unrelated parallel machine scheduling with resources; Variable neighborhood search;

Full Text:


DOI: http://doi.org/10.11591/ijai.v12.i1.pp315-327


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

IAES International Journal of Artificial Intelligence (IJ-AI)
ISSN/e-ISSN 2089-4872/2252-8938 
This journal is published by the Institute of Advanced Engineering and Science (IAES) in collaboration with Intelektual Pustaka Media Utama (IPMU).

View IJAI Stats