考虑时空约束的多层级产品生产调度方法

摘要

本发明公开了一种考虑时空约束的多层级产品生产调度方法，针对多层级产品的生产批量确定和机器调度问题，考虑了多层级产品固有的层级之间的间隔期(时间)约束，以及设备内部的空间约束，首先按照重要度对产品外部需求进行分解排产并按照BOM展开，再建立资源搜索引擎，按照不同的排产原则对展开的需求进行启发式搜索排产。当选择某台设备生产待满足需求时，同时考虑当期是否有足够的子项零件可用和设备容量对工装数量的限制。该方法基于松弛-固定算法解决实际工厂的大规模问题，且具有较快的求解速度和较高求解精度。

权利要求

1.一种考虑时空约束的多层级产品生产调度方法，其特征在于，包括以下步骤：

导入外部需求数据和每个产品参数，根据所述每个产品参数自动判断在无限产能的情况下，预设需求时期是否满足生产当前产品所需的最小成产时期，若能，则继续执行，若不能，则将所述预设需求时期自动推迟到所述最少时期；

人工预设算法参数，并选择排产原则，其中，所述算法参数包括每个产品分解切片大小的上限和每个产品的重要度；

在所述每个产品分解切片大小的上限内，按照随机公式生成每个产品当前次切边大小，按照所述重要度依次对每个产品的需求进行切片，并对当前次轮到的产品按照所述每个产品参数展开并准备排产；

选择生产时期和设备，将切片后的产品自BOM底层零件向上排产；以及

判断是否全部需求均生产完毕或均无法排产，若是，则结束算法并输出结果，若不是，则继续下一产品的排产。

2.根据权利要求1所述的考虑时空约束的多层级产品生产调度方法，其特征在于，导入所述外部需求数据和所述每个产品参数后，通过嵌套迭代推算所述最小生产时期，使得所述最小生产时期与导入的所述外部需求数据中预设需求时期进行对比。

3.根据权利要求1所述的考虑时空约束的多层级产品生产调度方法，其特征在于，所述排产原则由使用者根据生产实际条件自主选择，包括尽早生产、准时生产和尽早生产及准时生产的混合排产。

4.根据权利要求1所述的考虑时空约束的多层级产品生产调度方法，其特征在于，根据三种不同原则选择所述生产时期，当策略为尽早生产时，则从第一期开始选择；当策略为准时生产时，则从待生产零件的生产时期选择；当策略为混合生产时，则根据循环次数人工设置。

5.根据权利要求4所述的考虑时空约束的多层级产品生产调度方法，其特征在于，选择所述生产时期时，还判断当前零件的子项是否有足够数量在生产间隔前已生产。

6.根据权利要求1所述的考虑时空约束的多层级产品生产调度方法，其特征在于，所述设备的选择包括：判断当前设备是否还能接收本零件，和所述当前设备中已有零件的材料体系是否与所述本零件相同；

若条件均满足，则在所述当前设备放置一个零件，若任一项不满足，则循环判断至当前次分解出来的需求均被满足或无法再继续排产。

7.根据权利要求6所述的考虑时空约束的多层级产品生产调度方法，其特征在于，采用计算系数方法判断所述当前设备是否还能接收所述本零件，其中，针对不同形状的工装，在计算加工所需面积时，若工摆放占用比设定面积更多面积时，则取大于1的计算系数。

8.根据权利要求1所述的考虑时空约束的多层级产品生产调度方法，其特征在于，采用两种启发式搜索方法对当前需求进行排产，第一种，按照当前搜索，再向之前的时期搜索，若未满足所述当前需求，再向之后的时期进行搜索，第二种，从第一期开始搜索。

说明书

考虑时空约束的多层级产品生产调度方法

技术领域

[0001] 本发明涉及车间生产批量及机器调度技术领域，具体涉及的是并行机环境下，多层级产品的生产批量确定及机器调度方法，特别涉及一种考虑时空约束的多层级产品生产调度方法。

背景技术

[0002] 生产批量及机器调度问题广泛存在于离散型制造企业，属于典型的混合整数规划问题，且已被证明为NP-hard问题。生产批量及机器调度问题不仅要考虑某个时间段要生产多少产品，同时还要确定产品在机器上的加工顺序和数量。至今，已有众学者对生产批量问题在各类车间环境下开展广泛研究，并设计各类算法对其进行求解，包括精确算法(如动态规划算法、分支定界算法)，智能优化算法(如模拟退火算法)，以及启发式算法(如松弛-固定算法)，等等。虽然精确算法在理论上能够产生问题的最优解，但是在实际运用中，精确算法针对大规模问题往往无法保证在多项式时间内能够得到最优解，甚至计算机会存在内存溢出的现象。因此，利用启发式算法，对实际的大规模问题进行求解，并合理评估解的质量，是亟待解决的问题。

发明内容

[0003] 本发明旨在至少在一定程度上解决相关技术中的技术问题之一。

[0004] 为此，本发明的目的在于提出一种考虑时空约束的多层级产品生产调度方法，该方法基于松弛-固定算法的启发式算法，具有较快的求解速度和较高求解精度。

[0005] 为达到上述目的，本发明提出了考虑时空约束的多层级产品生产调度方法，包括以下步骤：导入外部需求数据和每个产品参数，根据所述每个产品参数自动判断在无限产能的情况下，预设需求时期是否满足生产当前产品所需的最小成产时期，若能，则继续执行，若不能，则将所述预设需求时期自动推迟到所述最少时期；人工预设算法参数，并选择排产原则，其中，所述算法参数包括每个产品分解切片大小的上限和每个产品的重要度；在所述每个产品分解切片大小的上限内，按照随机公式生成每个产品当前次切边大小，按照所述重要度依次对每个产品的需求进行切片，并对当前次轮到的产品按照所述每个产品参数展开并准备排产；选择生产时期和设备，将切片后的产品自BOM底层零件向上排产；判断是否全部需求均生产完毕或均无法排产，若是，则结束算法并输出结果，若不是，则继续下一产品的排产。

[0006] 本发明实施例的考虑时空约束的多层级产品生产调度方法，同时考虑时间和空间两个维度的能力，对已有研究问题在能力约束方面的一个拓展，具有重要的理论意义，另外，本发明实施例为线性增长，针对现实规模和大规模问题求解十分高效，充分考虑工作人员的领域知识，使得快速求解的同时确保解质量满足工作人员预期。

[0007] 另外，根据本发明上述实施例的考虑时空约束的多层级产品生产调度方法还可以具有以下附加的技术特征：

[0008] 进一步地，在本发明的一个实施例中，导入所述外部需求数据和所述每个产品参数后，通过嵌套迭代推算所述最小生产时期，使得所述最小生产时期与导入的所述外部需求数据中预设需求时期进行对比。

[0009] 进一步地，在本发明的一个实施例中，所述排产原则由使用者根据生产实际条件自主选择，包括尽早生产、准时生产和尽早生产及准时生产的混合排产。

[0010] 进一步地，在本发明的一个实施例中，根据三种不同原则选择所述生产时期，当策略为尽早生产时，则从第一期开始选择；当策略为准时生产时，则从待生产零件的生产时期选择；当策略为混合生产时，则根据循环次数人工设置。

[0011] 进一步地，在本发明的一个实施例中，选择所述生产时期时，还判断当前零件的子项是否有足够数量在生产间隔前已生产。

[0012] 进一步地，在本发明的一个实施例中，所述设备的选择包括：判断当前设备是否还能接收本零件；判断所述当前设备中已有零件的材料体系是否与所述本零件相同；若条件均满足，则在所述当前设备放置一个零件，若任一项不满足，则循环判断至当前次分解出来的需求均被满足或无法再继续排产。

[0013] 进一步地，在本发明的一个实施例中，采用计算系数方法判断所述当前设备是否还能接收所述本零件，其中，针对不同形状的工装，在计算加工所需面积时，若工摆放占用比设定面积更多面积时，则取大于1的计算系数。

[0014] 进一步地，在本发明的一个实施例中，采用两种启发式搜索方法对当前需求进行排产，第一种，按照当前搜索，再向之前的时期搜索，若未满足所述当前需求，再向之后的时期进行搜索，第二种，从第一期开始搜索。

[0015] 本发明附加的方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。

附图说明

[0016] 本发明上述的和/或附加的方面和优点从下面结合附图对实施例的描述中将变得明显和容易理解，其中：

[0017] 图1为根据本发明实施例的考虑时空约束的多层级产品生产调度方法流程图；

[0018] 图2为本发明实施例具体实施方式的算法流程图；

[0019] 图3为本发明实施例具体实施方式的算例图。

具体实施方式

[0020] 下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，旨在用于解释本发明，而不能理解为对本发明的限制。

[0021] 下面参照附图描述根据本发明实施例提出的考虑时空约束的多层级产品生产调度方法。

[0022] 图1是本发明一个实施例的考虑时空约束的多层级产品生产调度方法流程图。

[0023] 如图1所示，该考虑时空约束的多层级产品生产调度方法包括以下步骤：

[0024] 在步骤S1中，导入外部需求数据和每个产品参数，根据每个产品参数自动判断在无限产能的情况下，预设需求时期是否满足生产当前产品所需的最小成产时期，若能，则继续执行，若不能，则将预设需求时期自动推迟到最少时期。

[0025] 也就是说，导入外部需求数据 以及各产品参数(如BOM参数，子项到父项的间隔期，各工件工装大小，设备大小，等等)，并根据各零件到父项的间隔期，自动判断在无限产能的情况下在需求时期及之前是否能够满足需求，若不能，则将需求自动推迟到最近可以完成的时期。

[0026] 进一步地，在本发明的一个实施例中，导入外部需求数据和每个产品参数后，通过嵌套迭代推算最小生产时期，使得最小生产时期与导入的外部需求数据中预设需求时期进行对比。

[0027] 具体地，如图2所示，导入外部需求数据 以及产品参数，其中j＝1,…,J代表产品集合，i＝1,…,I代表产品的直接子项，t＝1,…,T为特定的需求时期。同时，需要导入的还有产品参数，比如BOM数据，子项-父项之间的加工提前期(如子项加工之后需要的静置时期，以及后续的处理过程所需时期)，各工件工装大小，工装数量，设备大小，等等。基于上述数据，利用嵌套算法迭代出各产品在无限产能下生产需要的最短时期Tmin，并与其导入的需求时期Td对比。若Tmin>Td，则说明产品其固有特性决定其至少需要Tmin期才能生产完成，而在目前的需求节点一定无法按时交货，因此需要将Td推迟到Tmin。另外，若Tmin>T，则拉长计划期至至少Tmin及以上。

[0028] 在步骤S2中，人工预设算法参数，并选择排产原则，其中，算法参数包括每个产品分解切片大小的上限和每个产品的重要度。

[0029] 进一步地，在本发明的一个实施例中，排产原则由使用者根据生产实际条件自主选择，包括尽早生产、准时生产和尽早生产及准时生产的混合排产。

[0030] 也就是说，人工设置算法参数，包括各产品的分解切片大小上限、产品重要度。设置完成后，j＝1,…,J即按照重要度进行降序排列。在本发明实施例中，先对重要度高的产品进行切片排产。同时，需要选择排产原则，包括“尽早生产”和“准时生产”，或“混合生产”，排产原则由下述步骤S4详细说明。

[0031] 在步骤S3中，在每个产品分解切片大小的上限内，按照随机公式生成每个产品当前次切边大小，按照重要度依次对每个产品的需求进行切片，并对当前次轮到的产品按照每个产品参数展开并准备排产。

[0032] 也就是说，在各产品分解切片大小的范围内，按照公式Rand(1,Max)随机生成各产品本次切片大小，按重要度的顺序，对各产品的需求进行切片，并对本次轮到的产品按照BOM展开并准备排产。

[0033] 具体地，如图3所示，假设需要在t＝10的时候交付3个G产品，工件生产提前期均为1。那么可以根据BOM关系，推导出需要在t＝4的时候交付3个A、B、C产品，在t＝6的时候交付
3个D和E产品，在t＝8的时候交付3个F产品。之后，再把这些作为需求进行需求更新。

[0034] 在步骤S4中，选择生产时期和设备，将切片后的产品自BOM底层零件向上排产。

[0035] 进一步地，在本发明的一个实施例中，根据三种不同原则选择生产时期，当策略为尽早生产时，则从第一期开始选择；当策略为准时生产时，则从待生产零件的生产时期选择；当策略为混合生产时，则根据循环次数人工设置。

[0036] 进一步地，在本发明的一个实施例中，选择生产时期时，还判断当前零件的子项是否有足够数量在生产间隔前已生产。

[0037] 也就是说，选择生产时期以及设备，对切下来的产品自BOM底层零件向上进行排产。选择生产时期根据三种不同的原则，当策略为“尽早生产”时，从第一期开始选择；当策略为“准时生产”时，从该零件应该生产的时期进行选择；当策略为“混合”时，根据循环次数而异(可人工设置)。同时，选择生产时期时，需要判断当期该零件的子项是否有足够数量在提前期之前已生产。

[0038] 具体而言，在对某零件进行排产时，需要检索其既定生产时期，再根据不同排产策略进行实际排产时期的选择。以图3中产品为例，在t＝6的时候需要交付3个D产品，若为“尽早生产”，则从t＝1开始测试当期是否能产出D产品，一直到产完此需求；若为“准时生产”，则从t＝6开始判断是否能产出D产品，若产不完此需求，那么开始先向前搜索至第一期，若仍然无法满足，则向后搜索(导致延期交货)。“混合生产”原则为，某些零件或某次排产按照“尽早”原则，某些按照“准时”原则，混合原则随算例变化，非固定原则。

[0039] 进一步地，在本发明的一个实施例中，设备的选择包括：

[0040] 判断当前设备是否还能接收本零件，和当前设备中已有零件的材料体系是否与本零件相同；

[0041] 若条件均满足，则在当前设备放置一个零件，若任一项不满足，则循环判断至当前次分解出来的需求均被满足或无法再继续排产。

[0042] 进一步地，在本发明的一个实施例中，采用计算系数方法判断当前设备是否还能接收本零件，其中，针对不同形状的工装，在计算加工所需面积时，若工摆放占用比设定面积更多面积时，则取大于1的计算系数。

[0043] 进一步地，在本发明的一个实施例中，采用两种启发式搜索方法对当前需求进行排产，第一种，按照当前搜索，再向之前的时期搜索，若未满足当前需求，再向之后的时期进行搜索，第二种，从第一期开始搜索。

[0044] 具体地，如图2所示，设备的选择需要按照如下步骤判断：

[0045] 步骤S401，判断设备是否还能放得下本零件。本发明实施例采用简单累加法，并结合计算系数进行估算处理，即对于某设备g(g＝1,…,G)，令 为零件i在设备g内生产的数量，fi为零件i对应工装的面积，sg为设备g的面积，li≥0为工装面积的计算系数，那么要求即设备内所有零件的工装面积相加不得超过设备面积。

[0046] 需要说明的是，本发明实施例利用工装面积系数li来对工装的形状和摆放难易程度进行估算，即，若某工装形状较为特殊，与其它零件共同加工时需要占据更多面积，则li应取大于1的系数。

[0047] 步骤S402，判断设备已有零件的材料体系是否与本零件相同，相同材料的零件才可以合并进同一设备加工。若条件均满足，则在相应设备放入一个该零件，若该零件在本次循环仍有需求未满足，则继续循环搜索。若本次分解出来的需求均被满足或无法再生产，跳转至步骤S5。

[0048] 在步骤S5中，判断是否全部需求均生产完毕或均无法排产，若是，则结束算法并输出结果，若不是，则继续下一产品的排产。

[0049] 根据本发明实施例提出的考虑时空约束的多层级产品生产调度方法，同时考虑时间和空间两个维度的能力，对已有研究问题在能力约束方面的一个拓展，具有重要的理论意义，另外，本发明实施例为线性增长，针对现实规模和大规模问题求解十分高效，充分考虑工作人员的领域知识，使得快速求解的同时确保解质量满足工作人员预期。

[0050] 此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括至少一个该特征。在本发明的描述中，“多个”的含义是至少两个，例如两个，三个等，除非另有明确具体的限定。

[0051] 在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结合和组合。

[0052] 尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述实施例进行变化、修改、替换和变型。