资质受限的多重资源并行排期算法研究

发布时间：2021-08-02 22:29

　　本文以计量校准实验室的任务调度作为现实应用背景,抽象出资质受限的多重资源并行排期问题模型。该模型也可以应用在其它业务场景中,例如,当互联网金融服务平台针对大量融资申请项目组织内外专家联合评审时,可以基于该模型采用高效的排期算法来合理地安排日程。资质受限的多重资源并行排期问题,可以视为车间调度问题的一个新型变种。现有的对资质受限车间调度问题的研究,普遍把机器作为唯一一种受到资质限制的必需资源,其研究重点在于机器的资质限制类型、包括资质在内的多种限制条件的组合以及多个优化目标的组合上。因此,相关的研究成果难以应用到资质受限的多重资源并行排期问题上。本文针对这种新型问题的特征,设计了支持多重资质受限和基于“加工机会”考量的动态柔性度量方法,分析了该问题在单位加工时间和任意加工时间两种情况下的求解模型和框架,提供了一系列以最小化时间表长为目标的精确算法和启发式算法,并通过较大规模的数值实验进行了算法测评。本文的主要研究成果如下:第一,提出了一种新型动态柔性度量方法,这种度量方法相对于既有算法在资质饱和度不均匀情况下更有优势。第二,首次明确定义和表示了工件加工时间为单位时间、两种必需资源受资质限... 

【文章来源】：北京大学北京市 211工程院校 985工程院校 教育部直属院校

【文章页数】：80 页

【学位级别】：硕士

【部分图文】：

算法3.1.2-1流程图

第三章支持多重资质受限的动态柔性度量方法17图3.1算法3.1.2-1流程图3.2多重资质受限及资质饱和度参照DF-Responsibility，如果多种必需资源受资质限制，工件面向每种资源都可以计算出一个柔性值，此时就需要决定如何处理这些柔性值得到工件的综合柔性。由于对此类问题的研究非常稀少，目前尚未发现有公开文献做相关的讨论。本文在后续的算法设计中，选取面向各种资源计算所得柔性值的最小值作为工件的综合柔性。因为在多种必需资源受资质限制的情况下，只有面向全部资源种类都具备较好的柔性，对实际提高工件的灵活性才是有意义的。另外一种情况对柔性度量方法的设计也有重要的影响。在现实应用场景中，机器或工人等资源个体的加工能力是有差异的，例如在计量校准实验室中，可能某些资深工程师具备十分丰富的技术资质，而某些实习工程师只具备有限的技术资质。为了模拟这种情况，本文在数值实验中设计了一个称为资质饱和度的参数α。所谓资质饱和算法结束算法开始计算所有的JFj和MFj所有工件已安排完毕？在JFj>0且JFj值最小的工件中随机选择一个安排当前选择的工件在尽可能早的轮次加工在该轮次MFi最小的备选机器中随机选择一个否是

表3.3中case1与表3.1中α=0.3的结果比较


本文编号：3318383