题目：不确定生产环境下面向干扰的若干重调度问题研究

实际生产环境中会随时遭遇到各种干扰的影响，如紧急订单到达、机器故障、因质检不达标而返工、订单撤销、释放期变更，等等。影响显著的突发干扰往往导致原有调度方案执行起来不再高效，甚至不再可行，此时亟需对原调度进行响应式修复或调度再生成；于是便引出生产运作中的重新调度问题。生产重调度是根植于生产实践的一项车间层优化决策活动，其调度结果直接关系到制造型企业在利润、生产率、市场竞争力，乃至客户满意度上的表现；近年来备受国内外生产调度学者与实践人士的关注，吸引着越来越多的研究兴趣。为了既高效又经济地实施重调度，通常要根据实际工况在调度性能、稳定性以及干扰响应速度三个维度上做出权衡决策。对于扰后生成的新调度，不仅追求少牺牲原调度目标上的优化水平，而且尽量控制或减少新、原调度之间的偏差程度。在细致、全面地回顾、梳理已有生产重调度研究文献的基础上，本文围绕着生产实践中几类常见的干扰事件，在三种常见的机器配置环境(单机、同速机与开放式车间)下，通过在每项重调度过程中妥善均衡或兼顾性能与稳定性，并借助于优化解法与仿真分析两种有代表性的研究思路，对于如何高效率、低成本地执行扰后重调度活动这一议题进行了较为系统的研究。具体来讲，本文的主要研究内容和成果可总结为如下六个方面：1、针对突发的新工件到达干扰，研究了总序位干扰量受上限、最小化最大延迟时间的单机重调度问题。首先，建立起若干结构化占优性质以及针对部分排序的两种下界计算式；随后，开发出了两阶段的构造型启发式算法、利用已有性质与下界的、精确的分支定界算法，以及基于变邻域搜索技术和问题特征的元启发式算法。通过数值实验对比考察了分支定界算法在较小规模算例上的计算效率，分析了两阶段启发式算法、变邻域搜索算法在较大规模算例上的解质量、效率以及适用条件。2、针对单机环境中的新工件到达干扰，研究了兼顾工件的线性恶化效应与序位相关学习效应的新型重调度问题。文中分别取完工期、最大序位干扰量为调度性能、稳定性的衡量指标；对于恶化与学习效应的处理，取某工件的实际工时为其开工时间的增函数，同时也为其所处序位的减函数。两种新重调度问题形式被构建出来：其一在初始工件的最大序位干扰量受上限的条件下追求调度完工期的最小化；另一则以最小化完工期与最大序位干扰量的线性组合为调度优化目标。借助建立起的支持性引理，对于两种新型重调度问题分别开发了多项式时间内可解的有效算法，并证明了各自算法的正确性。3、为了响应同速并行机环境下的一批工件重新返工干扰，在具备最小总完工时间值的初始调度基础上研究了如何妥善实施重调度活动。具体地，总完工时间与受扰工件数为相冲突双重调度准则；其中，总完工时间为重调度性能衡量指标；“受扰工件数”则统计新、原调度方案上被分配至不同机器上的工件数目，并用以衡量扰后新调度的稳定性。在层次和同时优化思想的指导下，构建了三个新型的双目标调度问题；对于实行字典序优化的两个重调度问题，开发了具备多项式时间复杂度的有效算法；对于总完工时间和受扰工件数的全部有效调度解的生成过程，也可在多项式时间内完成。最后，通过一个简单的算例演示，说明了三种所提算法的执行流程。4、针对开放式车间中单一突发的机器不可用干扰，进行了响应式的重调度方法研究。从右移、部分和全局重调度三种典型的重调度策略入手，提出并实现了三种重调度方法，用以修复初始调度或重新生成新的可行调度。对于重调度的绩效衡量，取完工期为重调度性能衡量指标；重调度稳定性则体现在工序开始时间偏差和序位偏差上。仿真实验中，通过模拟大量不同的重调度情景，考察、比较了三种方法在相同情景下的各自指标绩效。实验结果统计性地揭示出，特定重调度情景下若干有关于方法选取的适用性建议。5、针对开放式车间中的机器不可用干扰及其引发的工时缩减现象，分别基于右移、受影响工序、全局三种典型的重调度机制，提出并实现了三种特定的重调度方法以响应所关注的生产干扰：即sRSR、sAOR和sTR_GOS。对于重调度实施的绩效度量，重调度性能由总完工期来度量；而稳定性则体现在序位偏差和结束时间偏差上。在仿真实验中，通过模拟大量的重调度情景，考察了原调度生成机制的选取问题，并对比了三种方法在相同情景下的各自绩效。通过分析实验数据，在得出一系列总体性绩效对比结论的同时，还揭示出针对特定重调度情景的方法适用性统计结论与建议。6、针对急件到达干扰下的开放式车间重调度任务，从匹配式调度思路入手，考虑了面向分离式空闲时间(S方式)与连续式空闲时间(C方式)两种确定重调度时域的方式，提出了时域内求解约简式调度问题的两种启发式算法，即SRSSR_H1和SRSVSR_H1；进而形成了四种可行、备选的重调度实施方案。对于重调度的绩效衡量，从综合性能(兼顾扰后完工期和急件的及时完工情况)、扰前与扰后间的序位相似性两方面分别设定了相应指标。在仿真实验中，通过大量模拟急件干扰下的重调度情景，对四种实施方案各自的重调度绩效进行了同情景独立观测。实验结果表明：在四种实施方案的比较中，[S, SRSVSR_H1]和[C, SRSVSR_H1]的重调度绩效显著优于另两种方案；当干扰出现在早期时，建议选取方案[S, SRSVSR_H1]执行扰后重调度。