Hybrid genetic algorithm for permutation flowshop scheduling problems with total flowtime minimization

作者：Zhang Yi^*; Li Xiaoping; Wang Qian

来源：European Journal of Operational Research, 2009, 196(3): 869-876.

DOI：10.1016/j.ejor.2008.04.033

• Genetic algorithm
• Permutation flowshop
• Total flowtime
• Scheduling

In this paper, a HGA (hybrid genetic algorithm) is proposed for permutation flowshop scheduling problems (PFSP) with total flowtime minimization, which are known to be NP-hard. One of the chromosomes in the initial population is constructed by a suitable heuristic and the others are yielded randomly. An artificial chromosome is generated by a weighted simple mining gene structure, with which a new crossover operator is presented. Additionally, two effective heuristics are adopted as local search to improve all generated chromosomes in each generation. The HGA is compared with one of the most effective heuristics and a recent meta-heuristic on 120 benchmark instances. Experimental results show that the HGA outperforms the other two algorithms for all cases. Furthermore, HGA obtains 115 best solutions for the benchmark instances, 92 of which are newly discovered.

• 出版日期2009-8-1
• 单位东南大学