● 摘要
生产计划重调度问题是非常具有实际意义的一类组合优化问题，在受到干扰之后进行重调度，除了优化普通的性能指标之外，还需要优化稳定性指标，因而通常可以建模为双目标优化问题。基于修复的约束满足算法通常基于一个完整的但不可行的初始解进行修复从而使其达到可行或最优，因而非常适合在重调度领域进行应用及改进研究。当前关于重调度和约束满足算法的研究多数都集中在单目标，且约束满足算法的研究多在人工智能领域。基于以上出发点，本文对基于修复的约束满足算法对重调度问题的求解进行了深入的改进研究，本文的创新点主要体现在以下几个方面：1. 在现有的修复约束满足算法基础上，研究了其在排序领域的代表问题——flow shop排序问题中的应用，经过对其变量表示方式、变量排序与值排序启发式方法、跳出局部极值方法的改进，使其很好地应用于生产排序问题，并体现出优越性。2. 对flow shop问题中因新作业到达而引起的重调度问题建立了双目标优化模型，模型同时考虑了优化性能——服务水平（加权总延误），以及重调度的稳定性指标——计划被调整前后作业在开工时间上的差异。为了便于使用单目标算法进行求解，将双目标模型进行分解，建立了分级模型。针对分级模型，提出了改进的双层结构修复法，该算法先使用改进修复法IRCS_WT对上层模型进行优化，再通过对服务水平进行适当松弛后，使用改进的时间差异修复法IRCS_TD对下层模型进行优化。针对分级模型中不同的目标函数，设计了不同的变量排序启发式方法和跳出局部极值方法，以改进修复法的搜索性能。3. 对于加工速度不同的并行机生产排序问题，建立了以新作业到达、因质量问题返工和机器故障三种较常见事件为干扰因素的重调度优化模型。首先建立仅发生一次机器故障的重调度双目标优化模型，其次对综合三种干扰因素的复杂重调度问题建立了双目标优化模型。针对单因素和多因素的并行机双目标重调度问题，分别提出了结合束搜索算法、邻域搜索算法的束结构改进修复法和基于未来事件表的修复法，充分利用束搜索和邻域搜索在避免局部极值和搜索方面的优势，并且对多因素重调度问题使用了混合策略作为调度策略，增加重调度的灵活性。4. 对一个以订单方式为主的柔性制造系统的高科技企业配送中心，考虑顾客对订单进行变更从而引起生产计划的重调度因素，建立了同时优化性能指标（订单延误）和重调度稳定性指标（计划变更）的双目标优化模型。并提出了基于变量排序启发式改进的修复算法，将计算结果与原算法进行了比较分析，验证了本文改进修复法的有效性和实用性。