Application Of A Hybrid Metaheuristic Algorithm For Unrelated Parallel Machine Scheduling Problem With Machine And Job Sequence-Dependent Setup Times

Abstract

Unrelated Parallel Machine Scheduling Problem with Machine and Job Sequence-dependent Setup Times is a popular NP-hard problem variant of sequencing and scheduling field. Genetic Bee Algorithm is an effective meta heuristics algorithm although there are few papers to prove its performance compared to other competitive algorithms. This paper analyzed the effectiveness of the Genetic Bee Algorithm on the problem as adding a field that this perspective algorithm can handle. With the proposed neighborhood search and parameter sets, the Genetic Bee Algorithm showed its effectiveness on the balance of exploration and exploitation stage by steadily escaping local optima to reach the best solution. The results showed a lower bound in the Relative Proportional Deviation (RPD) than other algorithms, at 2.33%. It also gave the RPD under 10% for all instances from 10 to 100 jobs and from 2 to 25 machines. The algorithm also has potential for improvement in future research by the selection of search engines.