基于启发式-遗传算法的混合流水车间成套订单问题

Whole-set order problem of hybrid flow shop based on heuristic-genetic algorithms

针对并行机带工艺约束的混合流水车间环境下的成套订单问题,提出一种基于分批调度策略的启发式遗传算法。首先,以最大化加权成套订单数为目标建立数学模型,对工件分批采用内层遗传算法生成初始调度;再以外层启发式规则转化目标为最大加权成套订单数,设计一种订单评价指标用于突破交货时间瓶颈;最后,内外层算法循环优化,直到不存在瓶颈即得到满意解。实例验证结果显示,启发式遗传算法能在20代以内得到每组最优调度,种群规模大于50时得到最优解的概率达到70%。对比实验结果显示,当问题规模增加到40个工件时,遗传算法求解时间显著增加,在不同问题规模中临界比最小(SCR)规则优化后的加权成套订单数均较启发式遗传算法更少。启发式遗传算法能在实际工程中够将加权成套订单数提高到1.5倍以上,使加工时间平均缩短5.1%。结果表明,启发式遗传算法能够改善成套订单问题在混合流水车间环境下易陷入局部最优的问题,可在大规模复杂混合流水车间的订货型企业中实现计划与生产同步,具有实际意义。

A heuristic-genetic algorithm based on batch scheduling strategy was proposed for the whole-set order problem in hybrid flow shop environment with process constrainted parallel machine. Firstly, a mathematical model was established with the objective of maximizing the number of weighted whole-set orders, and initial scheduling was generated by inner genetic algorithm applying to workpieces in batches. Then, the target was transformed to the maximum weighted whole-set order quantity by outer heuristic rules, and an order evaluation index was designed to break the delivery time bottleneck. Finally, the inner and outer algorithms were optimized circularly until there was no bottleneck, which means the satisfactory solution was obtained. Examples show that heuristic-genetic algorithm can obtain the optimal scheduling within 20 generations, and the probability of obtaining the optimal solution is 70% when the population size is larger than 50. The experimental results show that when the scale of the problem increases to 40 workpieces, the solving time of genetic algorithm increases significantly, and the number of whole-set orders optimized by Smallest Critical Ratio(SCR) rule is smaller than the heuristic-genetic algorithm in different problem sizes. Heuristic-genetic algorithm can increase the quantity of weighted whole-set orders to more than 1.5 times in practical engineering, and shorten the processing time by 5.1% on average. The results show that the heuristic-genetic algorithm can solve the problem that the whole-set order problems are easy to fall into local optimum in the hybrid flow shop environment, and can realize the synchronization of planning and production in the large-scale and complex hybrid flow shop ordering enterprises, which has practical significance.