Abstract: To solve the delay in delivery of orders caused by unqualified product in productive process,a dynamic substitute model for multi-class product was presented by considering the minimized substitute-cost and substitute-times among orders.According to the characteristics of problem,it was proved be NP complete problem.A dynamic product substitute algorithm based on Constraint Satisfaction was proposed.Based on constraint satisfaction technology,the dynamic substitute algorithm to solve this problem was proposed,which was formulated substitute mechanism according to product substitution between urgency levels and product levels of orders.The effectiveness and feasibility of proposed algorithm was tested with simulation examination,and the best solution could be obtained by satisfying the actual product condition.

Key words: constraint satisfaction, multi-class product, dynamic substitute rules, algorithms

摘要： 为解决订单在生产过程中因某动态因素导致其出现产品质量问题而无法按期交货的问题,建立了以最小化产品替补总成本和订单之间替补次数为目标的多等级产品动态替补模型;根据问题的特点,证明了该问题为NP完全问题;基于约束满足技术,提出求解该问题的动态产品替补算法。该算法旨在根据订单交货期紧急程度以及其中的产品等级进行产品替补以制定替补机制。通过实验验证了模型和算法的可行性和有效性,并且完全能在满足生产实际的条件下获得最优解。

关键词: 约束满足, 多等级产品, 动态替补机制, 算法