摘要
针对混合流水车间调度问题 (Hybrid Flow Shop Scheduling,HFSS)建立了混合整数规划模型 ,提出了遗传下降算法 (Genetic Descent Algorithm,GDA) .GDA与 HFSS工件在机器上最优分配规则相结合 ,不但能够产生初始可行解 ,而且保证交叉和变异后解仍然可行 ;同时在遗传算法中嵌入邻域下降策略 .为了验证 GDA算法的有效性 ,随机产生了 2 30组数据进行实验 .实验结果表明 :对于 HFSS问题 ,在小规模情况下 ,GDA算法与最优解之间的平均偏差为 0 .0 1 % ;对于较大规模的情况 ,GDA比 NEH算法平均改进 1 0 .45% .
This paper first formulates the hybrid flow shop scheduling (HFSS) problem using an integer programming model and then develops a genetic descent algorithm (GDA) for it. The proposed GDA is constructed by combining the optimal job-machine allocation rules with the appropriate genetic coding. This method can not only generate feasible initial solutions, but also guarantee the feasibility of solutions after genetic operations. In the meantime, neighborhood search is imbedded in the iteration process of the algorithm. In order to testify the effectiveness of GDA, simulation is done based on randomly generated 230 instances. Computational experiments show that: 1) for small size HFSS scheduling problems, the average deviation of GDA from the optimal solution is 0.01%; 2) for medium-large size problems, the performance of GDA is 10.45% better than that of NEH algorithm.
出处
《自动化学报》
EI
CSCD
北大核心
2002年第4期637-641,共5页
Acta Automatica Sinica
基金
霍英东青年教师基金
国家教育部优秀青年教师基金
国家自然科学基金 ( 70 1710 30 )
国家教育部骨干教师基金资助
中国科学院机器人学开放实验室课题
