基于免疫遗传算法的模糊柔性作业车间调度问题研究

发布时间：2018-08-06 15:10

【摘要】：车间调度涉及企业的生产计划、采购、仓库、销售等运作管理,作为生产系统的核心,车间调度方案的优化可以提高生产效益和设备利用率。由于产品趋于个性化,工艺路线更加多样化,迫切需要企业能够快速有效地实现小批量的定制化生产,提高生产系统的柔性已成为企业提升竞争力的主要手段之一。车间调度问题的研究大多是将各种参数假定为某个具体数值,此类确定性调度模型不能很好地反映实际生产情况。本文研究的模糊柔性调度能够更加准确地描述生产中的加工时间、交货期等在一定范围内不能精确描述的数值,有助于调度模型的完善。单独研究模糊和柔性的车间调度的成果已有很多,同时考虑两种特性将使问题变得复杂得多。而问题随着规模变大和约束增多会变得更加复杂,数学规划、规则启发式等方法受到限制,利用智能算法之间的混合有助于调度问题的解决,其中遗传算法由于操作简单,具有鲁棒性、兼容性好等优点,经常被用来和其他算法结合,本文采用的算法就是在免疫算法和遗传算法结合的基础上加以改进。本文针对考虑模糊加工时间和模糊交货期的柔性作业车间调度问题,使用加权目标值的方法构建了多目标模糊柔性作业车间调度模型,给出了改进的免疫遗传算法的设计流程。算法中染色体采用玄光男提出的实数串编码,并采用浓度抑制的自适应提取疫苗操作,提出了新型的采用模拟退火的疫苗接种操作,接种前先对疫苗片段上的等位基因运用检测策略进行判断,具体做法是对比新旧最优个体的对应基因位,若在记忆库中出现概率较小则严格控制交换,判断是否非法解后再决定选弃。若某基因位在连续几代的接种中疫苗基因无变化,进一步对比该基因位上出现过的其他数值所能构成最优个体,判断是否最优基因或者陷入局部最优。通过模拟退火以概率进行接种可有效地改善早熟收敛和局部搜索能力差的缺点,并加入记忆库弥补了固定的交叉变异的不灵活性。最后先通过参考文献的仿真实例证实了算法的可行性和有效性,接着以加工时间和满意度为指标对常用作标准算例的Kacem模糊柔性作业车间调度进行求解,和单目标的遗传算法的Pareto最优解比较,结果表明了该算法显著提高了全局搜索能力和收敛速度,再以加工时间和机器负荷为指标,用8?8和10?10实例进行测试,该算法比文献中的其他算法获得更好或相当的Pareto解。最后用极具欺骗性的Rastrigin函数作为Benchmark进行收敛性分析,与文献中的其他算法对比,证明了本文改进的免疫遗传算法在求解易陷入局部最优的问题时优于大部分算法,前期可快速地跳出局部收敛,并弥补了后期接近最优解时出现波动震荡的缺陷。
[Abstract]:Shop scheduling involves the operation management of production planning, purchasing, warehouse, sales and so on. As the core of production system, the optimization of shop scheduling scheme can improve the efficiency of production and the utilization of equipment. Because the products tend to be individualized and the process routes are more diversified, it is urgent for enterprises to realize the customization of small batch production quickly and effectively, and to improve the flexibility of the production system has become one of the main means to enhance the competitiveness of enterprises. Most of the researches on job shop scheduling problem assume various parameters as some specific value, and this kind of deterministic scheduling model can not well reflect the actual production situation. The fuzzy flexible scheduling studied in this paper can more accurately describe the processing time and the due date of production, which can not be accurately described in a certain range, which is helpful to the improvement of the scheduling model. There have been a lot of achievements on fuzzy and flexible job shop scheduling alone, and it will be much more complicated to consider the two characteristics at the same time. The problem will become more complex with the increase of scale and constraints, and the methods of mathematical programming, rule heuristics and so on are restricted. The use of the mixture of intelligent algorithms is helpful to solve the scheduling problem, in which the genetic algorithm is easy to operate. Because of its good robustness and good compatibility, it is often used to combine with other algorithms. The algorithm used in this paper is improved on the basis of the combination of immune algorithm and genetic algorithm. Aiming at the flexible job shop scheduling problem with fuzzy processing time and fuzzy due date, the multi-objective fuzzy flexible job shop scheduling model is constructed by using weighted target value method, and the design flow of the improved immune genetic algorithm is given. In the algorithm, the chromosome is encoded by real number string proposed by Xuan Guang male, and the adaptive extraction vaccine operation of concentration suppression is used. A new vaccination operation using simulated annealing is proposed. Before inoculation, the alleles on the vaccine fragments were judged by using the detection strategy. The specific method was to compare the corresponding gene sites of the new and the old optimal individuals. If the probability of appearing in the memory bank was small, the exchange would be strictly controlled. Decide whether the solution is illegal before you decide to abandon it. If there is no change in the vaccine gene in successive generations of inoculation, further comparison of the other values on the gene site can constitute the optimal individual, determine whether the optimal gene or fall into the local optimal. Inoculation with probability by simulated annealing can effectively improve premature convergence and poor local search ability, and add memory bank to make up for the inflexibility of fixed cross mutation. Finally, the feasibility and effectiveness of the algorithm are verified by a simulation example in reference. Then, the Kacem fuzzy flexible job shop scheduling, which is often used as a standard example, is solved by taking the processing time and satisfaction degree as the index. Compared with the Pareto optimal solution of the single objective genetic algorithm, the results show that the algorithm improves the global search ability and convergence speed significantly, and then takes the processing time and machine load as the index, and tests with 8 / 8 and 10 / 10 examples. This algorithm obtains better or equivalent Pareto solutions than other algorithms in literature. Finally, the Rastrigin function is used as the Benchmark to analyze the convergence. Compared with other algorithms in the literature, the improved immune genetic algorithm is superior to most of the algorithms in solving the problem which is prone to fall into local optimum. The early stage can jump out of the local convergence quickly and make up for the defect of wave oscillation when the latter is near the optimal solution.
【学位授予单位】：重庆交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TB497;TP18

【参考文献】