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

Munther H. Abed, Mohd Nizam Mohmad Kahar

Abstract


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 genetic algorithm with a single-based metaheuristics (SBH) 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. 

Keywords


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



DOI: http://doi.org/10.11591/ijai.v12.i1.pp%25p

Refbacks

  • There are currently no refbacks.


View IJAI Stats

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