-
摘要: 针对混合流水车间调度问题(Hybrid Flow Shop Scheduling,HFSS)建立了混合整数规 划模型,提出了遗传下降算法(Genetic Descent Algorithm,GDA).GDA与HFSS工件在机器上 最优分配规则相结合,不但能够产生初始可行解,而且保证交叉和变异后解仍然可行;同时在遗 传算法中嵌入邻域下降策略.为了验证GDA算法的有效性,随机产生了230组数据进行实验. 实验结果表明:对于HFSS问题,在小规模情况下,GDA算法与最优解之间的平均偏差为0.1%; 对于较大规模的情况,GDA比NEH算法平均改进10.45%.Abstract: 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-ma-chine 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.
-
Key words:
- Production scheduling /
- hybrid flow shop /
- genetic descent algorithm
计量
- 文章访问数: 2214
- HTML全文浏览量: 77
- PDF下载量: 1624
- 被引次数: 0