混合流水车间调度的遗传下降算法

针对混合流水车间调度问题(Hybrid Flow Shop Scheduling,HFSS)建立了混合整数规划模型,提出了遗传下降算法(Genetic Descent Algorithm,GDA).GDA与HFSS工件在机器上最优分配规则相结合,不但能够产生初始可行解,而且保证交叉和变异后解仍然可行;同时在遗传算法中嵌入邻域下降策略.为了验证GDA算法的有效性,随机产生了230组数据进行实验.实验结果表明:对于HFSS问题,在小规模情况下,GDA算法与最优解之间的平均偏差为0.1%;对于较大规模的情况,GDA比NEH算法平均改进10.45%.

A GENETIC DESCENT ALGORITHM FOR HYBRID FLOW SHOP SCHEDULING

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.