基于规则及多色集合的多品种订单调度方法

Multi-item Order Scheduling Method Based on Rule and Polychromatic-sets Theory

针对多品种订单生产企业多工序、多品种、中小批量的生产特点,以最小化订单总完工时间和平均流程时间为目标建立了订单调度模型.提出了一种按规则分配订单以及作业排序相结合的调度思想,并利用改进的非支配排序遗传算法——NSGAⅡ对问题进行求解.考虑到多品种订单的多重约束性,采用多色集合理论中的围道布尔矩阵对多品种订单中各作业加工关系作了约束化处理;同时,以双层染色体进行编码,可以有效降低染色体的空间和时间复杂度;采用置换和反转变异两种算子,缩小了算法搜索范围,避免了早熟现象.最后以典型的订单生产实例进行仿真实验,结果表明应用该算法收敛快、运算效率高,可以获得满意的Pareto解集.

With a consideration of the feature of multi- process, multi-item and small lot in an order-production enterprise, an order scheduling model was established to minimize the overall completion time of all orders and average flow time. A new integrated thought of multi-rule order assignment and job sequencing was proposed. An improved non-dominated sorting genetic algorithm Ⅱ （NSGA Ⅱ） was employed to solve this model. The contour matrix in polychromatic set theory was adopted to deal with the processing relationship of all jobs. Then double recoding was adopted to reduce time and space complex of chromosome. At the same time, the adopted inversion operators and hybrid mutation can reduce searching space and improve the algorithm premature properties. The typical order production simulation experiment results show that the algorithm converges faster with high computation efficiency, which can satisfy Pareto solution set.