Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (21): 47-50.DOI: 10.3778/j.issn.1002-8331.2010.21.013

• 研究、探讨 • Previous Articles     Next Articles

Effective hybrid differential evolution algorithms for lot-streaming flow shop scheduling problem

SANG Hong-yan1,PAN Quan-ke2,WU Lei2,PAN Yu-xia2   

  1. 1.School of Mathematics Science,Liaocheng University,Liaocheng,Shandong 252059,China
    2.School of Computer Science,Liaocheng University,Liaocheng,Shandong 252059,China
  • Received:2009-01-20 Revised:2009-03-23 Online:2010-07-21 Published:2010-07-21
  • Contact: SANG Hong-yan

批量流水线调度问题的混合差分进化算法

桑红燕1,潘全科2,武 磊2,潘玉霞2   

  1. 1.聊城大学 数学科学学院,山东 聊城 252059
    2.聊城大学 计算机学院,山东 聊城 252059
  • 通讯作者: 桑红燕

Abstract: A Differential Evolution(DE) scheduling algorithm is presented for solving the Lot-streaming Flow Shop Scheduling Problem(LFSP) with the objective of minimizing the total weighted earliness and tardiness.In the proposed algorithm,the Most Position Value(MPV) rule is applied to enable the continuous DE algorithm to be used in all kinds of sequencing problems,mutant individual is constructed by the optimal target individual,and trial individual is obtained through crossover of target and mutant individual.Then Simulated Annealing(SA) algorithm is presented to enhance the local searching ability.Finally,two hybrid algorithms are developed by combining the proposed DE and SA algorithms.The computational results show that the hybrid differential evolution algorithms presented is effective and efficient for the LFSP.

Key words: lot-streaming flow shop scheduling, weighted earliness and tardiness, differential evolution algorithm, simulated annealing algorithm, hybrid algorithm

摘要: 针对E/T指标的批量流水线调度问题,提出了差分进化调度算法。该算法采用基于实数的编码方式,利用最优目标个体的扰动产生变异个体,通过变异个体与目标个体的交叉产生试验个体,提高了最优目标个体信息共享,并结合模拟退火算法给出了两种混合求解策略。仿真试验表明了所得算法的可行性和高效性。

关键词: 批量流水线调度, E/T指标, 差分进化算法, 模拟退火算法, 混合算法

CLC Number: