Title :
Genetic Algorithm for Minimizing the Makespan in Hybrid Flow Shop Scheduling Problem
Author :
Su, Zhixiong ; Li, Tieke
Author_Institution :
Sch. of Econ. & Manage., Univ. of Sci. & Technol. Beijing, Beijing, China
Abstract :
This paper propose a genetic algorithm based on extended Giffler & Thompson (EGT) procedure for hybrid flow shop (HFS) scheduling problem. In this method, each individual represents a complete schedule. The crossover and mutation operators are designed based on EGT algorithm. This algorithm is also used to generate initial population. Therefore, the search space is restricted to the active schedule space. Last, the performance of this algorithm is analyzed by computational experiments using benchmark instances. The results suggest that the proposed algorithm can find optimal solutions for all the easy problems, while optimal or near-optimal solutions for relatively hard problems.
Keywords :
flow shop scheduling; genetic algorithms; integer programming; linear programming; minimisation; search problems; EGT procedure; HFS; benchmark instance; computational experiment; genetic algorithm; hybrid flow shop scheduling problem; initial population; integer linear programming; makespan minimization; mutation operator; search space; Algorithm design and analysis; Genetic algorithms; Genetic mutations; Job shop scheduling; Paper technology; Parallel machines; Performance analysis; Processor scheduling; Technology management; Textile industry;
Conference_Titel :
Management and Service Science, 2009. MASS '09. International Conference on
Conference_Location :
Wuhan
Print_ISBN :
978-1-4244-4638-4
Electronic_ISBN :
978-1-4244-4639-1
DOI :
10.1109/ICMSS.2009.5301354