摘要：The job shop scheduling problem (JSSP) is an NP-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 for solving JSSP, we present a food source as a discrete job permutation and use the discrete operation to generate a new neighborhood food source for employing a bee colony, an onlooker bee colony and ascout bee colony. Secondly, three mutation operations are proposed to make DABCapplicable for the job shop scheduling problem. Thirdly, the fast local search is used toenhance the individuals with a certain probability. Fourthly, the pairwise based local search is used to enhance the global optimal solution and help the algorithm to escape from the local minimum. Additionally, simulations and comparisons based on JSSP benchmarks are carried out, which show that our algorithm is both effective and efficient.
关键词：Artificial bee colony; job shop scheduling; memetic algorithm; local search
