A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem

Abstract

In this paper a discrete artificial bee colony (DABC) algorithm is proposed to solve the lot-streaming flow shop scheduling problem with the criterion of total weighted earliness and tardiness penalties under both the idling and no-idling cases. Unlike the original ABC algorithm the proposed DABC algorithm represents a food source as a discrete job permutation and applies discrete operators to generate new neighboring food sources for the employed bees onlookers and scouts. An efficient initialization scheme which is based on the earliest due date (EDD) the smallest slack time on the last machine (LSL) and the smallest overall slack time (OSL) rules is presented to construct the initial population with certain quality and diversity. In addition a self adaptive strategy for generating neighboring food sources based on insert and swap operators is developed to enable the DABC algorithm to work on discrete/combinatorial spaces. Furthermore a simple but effective local search approach is embedded in the proposed DABC algorithm to enhance the local intensification capability. Through the analysis of experimental results the highly effective performance of the proposed DABC algorithm is shown against the best performing algorithms from the literature. (C) 2010 Elsevier Inc. All rights reserved.