An efficient job shop scheduling algorithm based on artificial bee colony

Scientific Research and Essays

Minghao Yin¹ 

关键词:  ;    Artificial bee colony;    job shop scheduling;    memetic algorithm;    local search.;   

DOI  :  10.5897/SRE10.773

学科分类：社会科学、人文和艺术（综合）

来源: Academic Journals

【 摘 要 】

The job shop scheduling problem (JSSP) is anNP-hard problem of wide engineering and theoretical background. In this paper, a discrete artificial bee colony based memetic algorithm, named DABC, is proposed for solving JSSP. Firstly, to make artificial bee colony (ABC) suitable forsolvingJSSP, we present a food source as a discrete job permutation andusethe discrete operation to generateanew neighborhood food source for employingabee colony,anonlooker bee colony andascout bee colony. Secondly, three mutation operations are proposed tomakeDABCapplicable forthe job shop scheduling problem. Thirdly, the fast local search is usedtoenhancethe individuals with a certain probability. Fourthly, thepairwise based local search is used to enhance the global optimal solution and help the algorithm to escape fromthelocal minimum. Additionally, simulations and comparisons based on JSSP benchmarks are carried out, which show that our algorithm is both effective and efficient.

【 授权许可】

CC BY