修复式约束满足算法求解流水车间订单投放问题

Repair-based constraint satisfaction algorithm for an order release problem in flow shop environment

针对流水车间环境下受交货期影响的订单投放问题,通过建立以最小化总惩罚成本为目标的整数规划模型,对单个计划期内的订单投放和订单排序进行联合决策。针对问题的特点,提出改进的修复式约束满足算法(MRCS)对模型进行求解。算法结合问题的求解目标,采用改进的NEH(MNEH)算法产生初始解,基于惩罚函数的思想设计适应度函数,并定义了新的变量表示形式以及新增、变换、替换三种变量调整操作;在修复解过程中,考虑到解的冲突具有双重性,采用概率选择方式选择修复冲突变量集合,并设计了基于最大惩罚优先原则(PLP)的变量选择方法实现冲突最小化。实验结果表明,改进的修复式约束满足算法是能够在有限时间内实现订单投放总惩罚成本优化的一种有效方法。