A Genetic Algorithm for Permutation Flow-Shop Scheduling Problem.

People involved: Mahdi Eskenasi (M.A.Sc. Student)   Dr. Mehran Mehrandezh(supervisor) 

Abstract: Permutation Flow-Shop scheduling problem (PFSP) is one of the well-known NP-hard combinatorial optimization problems. During the last four decades, the problem has received considerable attention of many researchers. Many different genetic algorithms have been proposed for PFSP so far. I am developing a new genetic algorithm according to the principles of genetics in honeybees.

  From biological point of view two types of reproduction are observed in the colony of honeybees: one-parent reproduction and two-parent reproduction. More explicitly, a bee in the hive is either a drone (male bee) which has just one parent (the queen bee) developed from unfertilized eggs, or a worker bee (a female bee) which has a mother (queen bee) and a father (one of the ten to twenty drones mating with the queen bee during the mating flight). The queen bee herself is genetically similar to worker bees and their difference stems from a variation in diet. Similarly, as illustrated in the followings, an algorithm is constructed in which we have two sets of population: Population of drones and population of female bees (workers and the queen). Each population has its own evolution mechanism but these two sets of population are inter-related. Population of drones evolves based on modification of the queen bee and local search. The modification itself consists of two phases: partially destruction of queen and construction of drones based on NEH algorithm. Evolution of drones, therefore, is based on unary operators (similar to one-parent reproduction of drones in nature). Population of female bees evolves by means of the customized crossover (between the queen and a selected number of drones) and mutation operators existing in the literature.

Researchers have established some benchmark problems for PFSP in order to evaluate and compare the efficiency of different offered algorithms. The most common benchmark problems in the literature belong to Taillard. The performance of proposed algorithm is finally compared with that of other genetic algorithms existing in the literature.

Publications:

I have no papers. My technical reports submitted to Dr. Mehrandezh are listed as follows:

·        Technical Report on Survey of Job-Shop Scheduling Using GAs, submitted to Dr. Mehran Mehrandezh. November 2004.

·       Iterative NEH and its performance, submitted to Dr. Mehran Mehrandezh. April 2005.