论文部分内容阅读
生产调度问题作为经典组合优化问题,具有高度的计算复杂性和广阔的应用前景。经典生产调度问题假设加工环境稳定,初始最优加工时间表制定后可以顺利执行。然而现实生产过程中充满不确定性,机器维护、机器故障、工件优先级变化和新工件到达等事件单独或者组合发生,使得初始计划无法按计划执行。这些事件统称为干扰事件,在干扰事件发生后,如何以尽量小的代价恢复加工系统正常运行是干扰管理(Disruption Management)致力于解决的问题。对应于加工系统基本构成要素,干扰事件可以大致分为资源相关和任务相关,对初始计划造成不同的影响。针对不同类型干扰事件,准确量化干扰事件的扰动,基于此构建同时考虑初始优化目标和扰动目标的模型,并设计高效算法求得问题有效解集供决策者选择,是生产调度干扰管理问题的核心和难点问题。本论文的主要研究内容包括:(1)资源相关扰动的干扰管理研究。选择资源相关扰动中最具代表性的机器维护作为研究对象:在单机环境中针对机器维护,研究初始最优加工时间表是基于加权折扣最短加工时间优先规则的问题,使用相对于初始计划工件完工时间的延迟来度量扰动,建立同时考虑原目标和与扰动目标的模型,结合量子算法和非支配排序遗传算法优势设计混合算法进行模型的求解。在并行机环境中面对干扰事件为改变加工效率的机器维护,使用机器-工件重新分配来度量扰动,构建干扰管理模型。设计求解问题有效前沿的穷举算法,以及在此基础上更高效率地优化某特定指标函数的分支定界算法。(2)任务相关扰动的干扰管理研究。选择工件相关干扰事件中最具代表性的工件优先级变化和新工件到达作为研究对象:针对单机环境下存在安装时间的最优化工作流时间问题,研究工件优先级突发提高的应对,设计最近邻域和插入混合算法为非支配排序遗传算法提供较优初始解,最终求得高质量有效前沿。针对单机环境下工件加工时间可通过非线性资源消耗进行压缩的问题,研究单个新工件到达和处理依概率发生时的应对,基于工件吸收干扰影响的能力制定初始加工时间表,使得干扰发生后新时间表能尽快和初始计划完全匹配。针对单机环境下计划外多个新工件抵达,研究通过外包手段为加工服务承接商制定生产配送的集成优化方案,在运营成本和服务水平之间进行有效权衡。(3)资源相关扰动和任务相关扰动并发的干扰管理研究。以上述内容为基础,研究了机器维护和新工件达到同时发生时的干扰管理问题。将客户对于完工时间延迟的非对称感知考虑在扰动度量中,从而使新的解决方案更具现实意义。提出一种基于有效解的元启发式算法,其中部分初始种群是通过动态规划方式求得。为了检验该方法的性能,设计了计算机仿真实验,比较了重调度干扰策略和局部修复策略,分析了不同启发式算法和分派规则的性能。通过对数值仿真结果进行统计分析,并根据现有度量有效前沿质量指标进行计算,验证了重调度策略和设计方法的有效性。本研究属于排序理论、运筹学优化理论和智能优化算法的交叉渗透,对生产调度干扰管理这一难题进行了有益探索。为加工制造企业面对突发干扰事件在生产成本和系统扰动之间权衡决策提供理论支持,对企业提高服务质量具有重要现实意义,对丰富拓展生产排序理论和多目标智能优化算法研究领域具有重要理论意义。