加工时间具有随机性的Job Shop鲁棒调度问题研究

发布时间：2020-07-22 15:08

【摘要】：Job Shop制造环境中的不确定因素,如随机机器故障、刀具或物料短缺、工人熟练程度差异等,均会造成加工时间随机变化,这会导致调度实际执行效果偏离最优调度方案,严重情况下可能造成交货期、工人和原材料的配置等发生改变,从而影响车间的生产成本、系统稳定性和客户满意度。为保证加工时间随机变化条件下生产调度方案的稳定、高效执行,在优化调度性能的同时降低潜在扰动对调度性能的影响,研究加工时间具有随机性的Job Shop调度问题(Stochastic Job Shop Scheduling Problems,SJSSP)具有重要理论及实践意义。本文针对加工时间具有随机性的Job Shop调度问题,采用鲁棒调度的方法,系统研究了不同约束下基于加工时间场景的SJSSP鲁棒调度问题,为调度决策者快速提供兼顾性能和鲁棒性的调度方案。首先,考虑不确定因素对加工时间随机性的影响,研究了基于加工时间随机场景的SJSSP鲁棒调度问题;进而,针对工人负面主观因素导致的工人故意推迟开工或拖延而产生资源浪费和调度紊乱,研究了考虑工人负面主观因素的SJSSP鲁棒调度问题;最后,考虑实际制造环境中工人熟练程度对加工时间随机性的控制作用,研究了机器-工人双资源约束的SJSSP鲁棒调度问题。主要研究内容和成果如下:1.考虑加工时间随机性的SJSSP鲁棒调度问题建模根据SJSSP鲁棒调度子问题特点,采用对应的鲁棒调度方法建立了三种鲁棒调度模型。首先,采用期望性能作为鲁棒性评价指标建立基于加工时间随机场景仿真的SJSSP鲁棒调度模型(SJSSP robust scheduling based on stochastic scenarios of processing times,SJSSP-SSP);其次,考虑Job Shop制造系统中工人“学生综合症”和“帕肯森定律”两种典型负面主观因素,采用“轨道执行策略”降低工人负面主观因素对调度过程的不利影响,建立基于加工时间期望场景的SJSSP鲁棒调度模型(SJSSP robust scheduling based on expected scenarios of processing times,SJSSP-ESP);最后,考虑工人熟练程度对加工时间随机性的控制,建立机器-工人双资源约束下基于加工时间期望场景的SJSSP鲁棒调度模型(Dual-Resource Constrained SJSSP-ESP,DR-SJSSP-ESP)。2.基于加工时间随机场景仿真的SJSSP鲁棒调度研究提出了包含评价空间缩减策略的混合分布估计算法求解SJSSP-SSP。首先,为提升算法求解性能,提出一种基于分布估计算法(Estimation of Distribution Algorithm,EDA)的混合算法(HEDA)。进而,为提升SJSSP-SSP的求解效率,提出评价空间缩减策略(Reduction Strategy,RS),并嵌入HEDA构造改进的RS-HEDA。仿真结果表明HEDA的优化性能优于五种现有典型算法;RS-HEDA可在不降低优化性能的前提下,显著提升SJSSP-SSP的求解效率;通过制造企业调度案例的仿真,验证了模型和算法用于实际调度问题的有效性。3.基于加工时间期望场景的SJSSP鲁棒调度研究提出了基于鲁棒性代理指标的多目标优化算法求解SJSSP-ESP。首先,针对鲁棒性仿真评价效率低下的问题,利用加工时间的随机信息及调度方案的扰动吸收能力信息,提出了两种基于关键和非关键工序集的鲁棒性代理指标。针对此模型双目标优化的需求,提出了基于改进非支配排序的多目标HEDA。采用此算法,通过将所提出的鲁棒性代理指标与现有三种典型代理指标进行比较,验证了所提出的代理指标用于SJSSP-ESP鲁棒性评价的有效性。进而,采用多目标HEDA,将所提出的鲁棒性代理指标用于SJSSP-ESP鲁棒调度,并与基于仿真的鲁棒性指标在多个维度下进行对比,验证了所提出的鲁棒性代理指标在显著提升计算效率的同时可得到性能优异的Pareto解集。最后,通过制造企业调度案例的仿真,验证了所提鲁棒性代理指标和算法用于实际Job Shop鲁棒调度的有效性。4.机器-工人双资源约束下基于加工时间期望场景的SJSSP鲁棒调度研究提出了机器-工人两阶段指派方法和双资源约束下的鲁棒性代理指标,并采用多目标HEDA求解DR-SJSSP-ESP。首先,建立了工人熟练程度与加工时间随机性的关系模型;进而,提出了基于工人熟练程度和负载均衡的机器-工人两阶段指派策略;最后,为提高多目标HEDA鲁棒性评价的效率,在分析工序间加工时间扰动传播过程的基础上,提出基于扰动传播的鲁棒性代理指标。仿真实验验证了所提出的鲁棒性代理指标的有效性以及两阶段指派策略对于调度性能优势;进而,采用多目标HEDA,通过对DR-SJSSP-ESP进行Pareto鲁棒调度优化结果的分析,验证了采用所提出的指派策略和基于扰动传播的鲁棒性代理指标可得到性能优异的Pareto解集,且问题求解效率显著提升。最后,通过从制造系统中抽取的调度案例仿真,验证了所提指派策略和鲁棒性代理指标用于解决双资源约束下实际Job Shop鲁棒调度问题的有效性。
【学位授予单位】：西北工业大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：O224;F273
【图文】：

均值,鲁棒性,算例,当关

图 4-4 算例 FT10_SPT 在不同 UL 下的鲁棒性均值与 Makespan 均值变化图 4-5 算例 LA21_SPT 在不同 UL 下的鲁棒性均值及 Makespan 均值由图4-4和图4-5中右图中曲线可以看出，同等UL下，当关注鲁棒性，Makespan指标表现出最差鲁棒性；由左图中看出，当关注 Makespan，鲁棒性指标得到了最差 Makespan。在分析所提出的 SM-CO 的性能之前，先对图中 Makespan 随 UL 增加的趋势进行讨论。随着 UL 的增加，SM-CO 与 RMsim 优化得到的平均 Makespan值有降低的趋势。原因是更多的随机扰动工序带来更严重的随机扰动，调度结构中的松弛时间无法吸收

均值,鲁棒性,算例,当关

总体均值,算例

西北工业大学博士学位论文据低于 P-Set 对应数据，处于 28.57%~100%之间，表明两种指 Pareto 前沿中互不支配的 Pareto 解的比例更高。 SC (CO1,Sim明显低于 SC (Sim,CO1)对应的两组数据，例如对于 FT06_SPT，盖率分别为 42.21%和 93.75%，说明 RMsim 得到了更好的 Pa P-Front 对应的数据分别为 25%和 85.7%，同样说明了 RMsim比 RMsim 与 SM-CO2 的 P-Set 对应数据，8 组算例中有 6 组 R LA26_SPT 和 LA32_SPT 两组算例中其数值为 65.08%和 73的对应值 95.24%和 95.26%，说明总体上 RMsim 仍占据优势。对RMsim 同样占据优势。为对比各支配率指标的总体均值，给同 SC 关系下的总体均值对比曲线。

【相似文献】