兼顾紧急插入产品和在加工产品交货期的综合调度方法

摘要

兼顾紧急插入产品和在加工产品交货期的综合调度方法；本发明方法包括：将紧急插入的产品和在加工产品未加工工序用虚拟根节点连接构成一个新的虚拟重构工艺树，将工序数量最多的路径视为各产品的紧迫路径，其上的工序为紧迫工序；对于瓶颈设备上加工时间重叠的工序，根据产品优越度、工序的弹性优越度和拟合优越度，采用单产品择优策略和弹性综合评价策略确定产品中各工序的调度次序和开始加工时间。本发明用于考虑交货期的单件复杂产品中存在紧急插入产品时的综合调度。

说明书

技术领域

本发明涉及一种兼顾紧急插入产品和在加工产品交货期的综合调度方法。

背景技术

紧急插入产品定义：在产品生产加工过程中，存在某个时刻紧急插入的产品。

对于已有的有关交货期的综合调度算法，主要采用动态关键路径、拟关键路径以及长路径优先来进行调度顺序的确定，没有充分考虑到产品中总工序个数，产品优越度和不同产品内工序的弹性优越度对整个产品的工期的影响。

发明内容

本发明的目的是提供一种兼顾紧急插入产品和在加工产品交货期的综合调度方法：

上述的目的通过以下的技术方案实现：

将紧急插入的产品和在加工产品的未加工工序用虚拟根节点连接构成一个新的虚拟重构工艺树；计算产品的优越度、工序的弹性优越度和拟合优越度；采用单产品择优策略和弹性综合评价策略确定工序的调度次序和开始加工时间。

所述的兼顾紧急插入产品和在加工产品交货期的综合调度方法，所述的调度方法具体实施步骤如下：

步骤1：根据产品加工信息实际车间在加工产品P、N的未加工工序的工艺树和待插入产品M的加工工艺树；

步骤2：将紧急插入产品M和在加工产品P、N的未加工工序的工艺树，用虚拟根节点连接构成一个虚拟重构工艺树W，将工艺树W中所有工序设计为虚拟工序；

步骤3：将工序数量最多的路径视为各产品的紧迫路径，其上的工序为紧迫工序，若存在多条路径工序数量都相等，则长用时路径为紧迫路径；

步骤4：计算产品的优越度，将产品的紧迫工序按产品优越度从高至低存至紧迫工序组；

步骤5：将可调度工序存至可调度工序集中；

步骤6：判断可调度工序集合是否为空，若为空则转步骤12，否则转步骤7；

步骤7：可调度工序集中是否存在多道工序抢占同一设备，若是转步骤8，若否，转步骤11；

步骤8：判断冲突工序是否隶属同一产品，若是，计算冲突工序的弹性优越度，根据单产品择优策略确定工序的调度次序和开始加工时间，若否，转步骤9；

步骤9：判断冲突工序是否属于紧迫工序集，若是，优先调度产品优越度大的紧迫工序，若否，转步骤10；

步骤10：计算冲突工序拟合优越度，据弹性综合评价策略确定工序的调度次序和开始加工时间；

步骤11：将其存入拟排序调度工序集中，并在可调度工序集中删除本工序节点；

步骤12：根据拟排序调度工序集，输出调度结果甘特图。

有益效果：

1. 本发明通过对存在交货期的多产品综合调度的问题分析，在一些干扰因素存在的情况下，若产品中的工序数量越多，它对整个产品的完工时间产生的影响就会较大；反之，若产品中工序总数量越少，则影响产品完工工期的可能性就会越小，但同时也要考虑到产品的交货期，因此产品中的紧迫路径上工序的总数量及总时间、产品中工序总数量和产品交货期是衡量产品优越度的重要指标。

本发明对抢占同一设备的非紧迫工序采用（工序的弹性优越度*隶属产品的优越度）来评定冲突工序的拟合优越度大小，择优选择调度，根据影响产品优越度的因素和产生设备冲突工序的重要程度，进行评级。

附图说明：

附图1是本发明的兼顾紧急插入产品和在加工产品交货期的综合调度方法的流程图。

附图2是附图1中确定冲突工序解决方案的流程图。

附图3是附图1中确定产品调度的示意图。

附图4、5、6是紧急插入产品M和在加工产品P、N的未加工工序的工艺树图例。

附图7是本发明针对附图4、附图5、附图6所示工艺树用虚拟根节点连接构成一个新的虚拟重构工艺树W。

附图8是本发明针对附图4、附图5、附图6所示工艺树示例的调度结果甘特图。

附图9是现有技术针对附图7所示工艺树示例的调度结果甘特图。

具体实施方式：

实施例1：

一种兼顾紧急插入产品和在加工产品交货期的综合调度方法，在实际应用中有较多应用。将紧急插入的产品和在加工产品用虚拟根节点连接构成一个新的虚拟重构工艺树；计算各产品的优越度；对于可调度工序抢占同一设备的冲突调整，首先判断冲突工序组是否隶属于同一产品，还是不同产品间的工序产生的冲突，采用单产品择优策略和弹性综合评价策略确定冲突工序的调度次序。

实施例2：

上述的兼顾紧急插入产品和在加工产品交货期的综合调度方法，所述的调度方法具体实施步骤如下：

步骤1：根据产品加工信息实际车间在加工产品P、N的未加工工序的工艺树和待插入产品M的加工工艺树；

步骤2：将紧急插入产品M和在加工产品P、N的未加工工序的工艺树，用虚拟根节点连接构成一个虚拟重构工艺树W，将工艺树W中所有工序设计为虚拟工序；

步骤3：将工序数量最多的路径视为各产品的紧迫路径，其上的工序为紧迫工序，若存在多条路径工序数量都相等，则长用时路径为紧迫路径；

步骤4：计算产品的优越度，将产品的紧迫工序按产品优越度从高至低存至紧迫工序组；

步骤5：将可调度工序存至可调度工序集中；

步骤6：判断可调度工序集合是否为空，若为空则转步骤12，否则转步骤7；

步骤7：可调度工序集中是否存在多道工序抢占同一设备，若是转步骤8，若否，转步骤11；

步骤8：判断冲突工序是否隶属同一产品，若是，计算冲突工序的弹性优越度，根据单产品择优策略确定工序的调度次序和开始加工时间，若否，转步骤9；

步骤9：判断冲突工序是否属于紧迫工序集，若是，优先调度产品优越度大的紧迫工序，若否，转步骤10；

步骤10：计算冲突工序拟合优越度，据弹性综合评价策略确定工序的调度次序和开始加工时间；

步骤11：将其存入拟排序调度工序集中，并在可调度工序集中删除本工序节点；

步骤12：根据拟排序调度工序集，输出调度结果甘特图。

实施例3：

所述产品优越度，通过计算（产品的紧迫工序个数/产品总工序数）*（产品紧迫路径总时间/产品交货期）得出：产品中的工序数量越多对整个产品的完工时间产生的影响越大，以及产品紧迫路径上的工序数量最多，它们的有效调度会影响着整个产品的调度进程，但同时也要考虑产品的交货期也是衡量产品优越度的一个重要指标。

所述工序弹性优越度，通过计算（工序到根节点长路径上的工序个数/此刻隶属产品未调度工序的总数量）得出：处在不同时刻，产品中工序的加工情况是处在变化中，抢占同一设备冲突的工序，其到根节点长路径上的工序数量和隶属产品后续加工工序总数量可能不同，其次根据工序间的逻辑关系，工序的提前或拖期调度会影响着其后续工序的调度，因此冲突工序对隶属产品的完工工期造成的影响也不同；对于冲突工序间的择优调度选择，优先调度弹性优越度高的工序。

所述单产品择优策略：冲突工序包含紧迫工序，优先调度紧迫工序，否则计算冲突工序的弹性优越度，若弹性优越度相等，比较冲突工序到根节点的最长路径用时，耗时长的工序优先调度，若最长路径用时也相等，加工耗时短的工序优先。

所述拟合优越度，通过计算（工序的弹性优越度*隶属产品的优越度）得出：当高优越度的产品的非紧迫工序和低优越度的产品的紧迫工序发生冲突时，仅考虑产品优越度，不会对高优越度的产品造成太大影响，但低优越度的产品的紧迫工序延期会造成该产品拖期完工，同理也不能只考虑工序弹性优越度；综合考虑到多产品间工序调度次序，优先调度拟合优越度高的工序。

所述弹性综合评价策略，若高优越度的产品中的紧迫工序和低优越度的产品中的工序产生冲突，高优越度的产品中的紧迫工序优先；若高优越度的产品中的非紧迫工序和低优越度的产品中的工序产生冲突，优先调度拟合优越度高的工序。

实施例4：

上述的兼顾紧急插入产品和在加工产品交货期的综合调度方法，基于虚拟加工工艺树调度模块：

将紧急插入的产品和在加工产品的未加工工序用虚拟根节点连接构成一个新的虚拟重构工艺树，计算产品的优越度，根据多工序路径和路径长用时确定产品的的紧迫路径及紧迫工序；然后分别对可调度工序集中产生抢占同一设备的工序，消解冲突，确定冲突工序的调度次序。

实施例5：

上述的兼顾紧急插入产品和在加工产品交货期的综合调度方法，基于综合调度中选取调度策略模块：

当发生多工序抢占同一设备的情况，采用单产品择优策略和弹性综合评价策略确定工序的调度次序和开始加工时间，调整冲突工序，确定可调度工序的顺序和开始加工时间，最后输出调度结果甘特图。

实施例6：

上述的兼顾紧急插入产品和在加工产品交货期的综合调度方法，本技术主要针对加工工艺树具有树形结构的复杂产品的综合调度任务，通常采用加工工艺树来表示，调度目标是在满足交货期的要求下，尽可能减少总工期时长。如附图4、5、6所示，每个节点表示工序节点的编号；每个节点包含加工设备、加工时长。加工工艺树图能够清晰明了地表示加工任务节点之间的关系。

以下将结合附图4、5、6中的工艺树图例来对本方法的具体执行流程进行说明。

实施例7：

上述的兼顾紧急插入产品和在加工产品交货期的综合调度方法，下面将用本调度方法对附图4、5、6中的工艺树图例执行调度。方法具体操作步骤如下：

步骤1：将紧急插入产品M和在加工产品P、N的工艺树，用虚拟根节点连接构成一个新的虚拟重构工艺树W，将工艺树W中所有工序设计为虚拟工序，如附图7所示；

步骤2：计算产品M、P、N的优先级：0.271,0,250,0,364；

步骤3：采用工序路径量级法，确定虚拟工艺树W上的产品M的紧迫路径M7-M5-M2-M1,产品N的紧迫路径N11-N10-N7-N5-N3-N1，产品P的紧迫路径P7-P5-P2-P1,紧迫工序组{N11,N10,N7,N5,N3,

N1,M7,M5,M2,M1, P7,P5,P2,P1}；

步骤4：根据重调度规划可调度工序集中，发生抢占同一设备冲突的工序，得到的优化调度方案如表1所示：

表1 重调度规划方案

步骤5：虚拟加工树W，采用单产品择优策略和弹性综合评价策略调整冲突工序，确定工序的调度次序和开始加工时间，调度顺序为M7,N9,N11,P8,M6,N6,N10,P7,N8,M5,M4,N7,M2,P

5,N4,P6,N5,P4,M3,P2,P3,N3,N2,P1,M1,N1，得到加工结束时间为230工时，产品的调度甘特图如图8所示。

实施例8：

上述的兼顾紧急插入产品和在加工产品交货期的综合调度方法，实例对比：

下面将本发明调度方法与现有的较为优秀的存在交货期约束的动态多产品调度方法进行实例对比。

附图9为采用现有的存在交货期约束的动态多产品综合调度方法针对附图4、附图5、附图6所示的产品加工树图例进行调度的结果甘特图，产品M、P、N紧迫度为0.475,0.5,0.667,产品调度次序分别为P7,N9,N11,P8,M7,N10,N6,N4,N8,P6,P5,N7,N2,P3,P4,M6,

P2,N5,M3,M5,P1,M4,N3,M2,N1,M1，通过对比附图8和附图9可以看出，采用本文提出的方法总完工时间是230工时，产品P、M、N的完工时间分别为195、190、230，满足各产品的交货期，采用现有的较为优秀的方法的总完工时间是245工时,产品P、M、N的完工时间分别为175、245、230，产品M完工时间超出交货期，产品M与产品P、N争夺设备资源，现有的算法把产品P、N先于产品M调度，在产品M的交货期内占用较长时间的设备资源导致产品M超越交货期,而本发明调度算法的优越度次序是N、M、P，同时采用的单产品择优策略和弹性综合评价策略，更为合理调度冲突工序，在尽量满足交货期完工的同时，缩短了总完工时间。

因此，本发明是全新的方法，用于加工工艺树具有树形结构特征的复杂产品的综合调度任务。