【
技术领域：
】一种排程方法，尤指一种多工序流程式产品生产排程方法。
背景技术：
：在纺织、制鞋等人力密集的产业中，一种产品的生产组装作业中包含多道工序，并且使用大量的人力组成连续的生产线进行产品由原料到成品的加工及组装。为了达到良好的生产效率，如何将人力适当的分配到各道工序中，便是每一个工厂在生产产品时必然面临的问题。在进行人力分配的过程中，还需考虑生产线中各该工序之间的条件及相对关系。举例来说，每一道工序所需的平均时间不相同，即相同人力在固定时间内进行每一道工序的效率不同。一般来说，一个工厂的生产效率定义为在固定时间内产出之完成品数量，而一件完成品的产出必须完整的通过所有工序。因此，完成品的数量受限于产能最低的该道工序的产出数量。换句话说，为了达到最佳的生产效率，各该工序的人力分配必须提高各道工序中产出数量最低的该道工序的产出数量，以提高完成品的产出数量。举例来说，一生产线在当天的人力配置下，其中第3工序一小时只能完成500件产品的加工，其他工序一小时能完成800件产品的加工，则该生产线一小时只能产出500件完成品，生产效率为500件/小时。在同一条生产在线，通过更改人力配置，其中第3工序一小时能产出550件产品，其他工序一小时能完成700件产品的加工，则该生产线一小时能产出550件完成品，生产效率提高为550件/小时。此外，各该工序中，工序种类相同且相邻的工序还可合并进行。在人力数量、生产工序及各该工序种类已知的情况下，通过将所有工序合并的可能与人力分配的可能与进行排列组合，以穷举法全部列出并计算其生产效率，则势必可以得到具有最佳生产效率的唯一最佳配置。然而，最佳生产效率生产排程的问题复杂程度具有np-hard问题特性，获得最佳配置所需之计算次数随人力数量或工序数量呈指数上升。进一步来说，每一工作天均有人员临时请假导致人力数量临时变动、部分工序提早完成等变量，因此若要达每一天都能达到最佳效率，每天开工前都必须计算一次较佳人力配置。举例来说，假设今日生产之产品之工序数量共15道，且有25人进行作业，则根据可合并之工序数量不同，所需计算次数在196万～96亿次之间；若今日生产之产品之工序数量共20道，且有25人进行作业，则所需计算次数在4.2万～8千亿次之间；若今日生产之产品之工序数量同样为20道，作业人数增加为30人，则所需计算次数在2千万～11兆次之间。也就是说，无论是工序数量或当天人力总数的变动，皆会使得通过穷举法取得人力配置的最佳方法的所需计算数量随大幅增加。而实际上，多数产品的工序数量往往大于30道，而单一工厂之人力数量往往大于1000人，通过上述穷举方法获得最佳配置之计算量是任何一般计算机皆无法在每日开工前的有限时间得到该较佳配置。综上所述，现有的生产排程方法势必须进行进一步改良。技术实现要素：有鉴于现有的产品生产排程方法的计算量庞大，难以在实际执行上根据每天的人力数量及工序变动在有限时间内获得符合效率标准的工序合并及人力分配排程，本发明提供一种多工序流程式产品生产排程方法，由一生产排程应用程序执行。该产品生产排程方法包含以下步骤：接收一产品种类信息，根据产品种类信息读取一产品基础信息数据库，该产品基础信息数据库包含一工序序号信息，以及对应该工序序号信息的一工序周期时间信息、一工序种类信息；根据该工序序号信息及该工序种类信息产生一有向网络模型；根据该有向网络模型产生一组流量限制式；接收一人力数量信息，根据该人力数量信息产生一人力限制式；读取一目标函式，并根据该组流量限制式、工序周期时间信息，计算该目标函式基于该有向网络模型之一最佳解，且输出对应该最佳解的一人力配置。该有向网络模型系根据该工序序号及对应的工序种类产生，而根据有向网络模型产生之该组流量限制式的数量受限于工序序号的数量，且不受人力数量的影响。通过根据有向网络模型及生产线顺序限制产生的有限的限制式，大幅降低获得最佳配置所需之计算次数，使得计算机能够实时根据当日人力及工序计算获得最佳配置。【附图说明】图1系本发明多工序流程式产品生产排程方法的流程示意图。图2系本发明多工序流程式产品生产排程方法的一有向网络模型的转运节点示意图。图3系本发明多工序流程式产品生产排程方法的一有向网络模型示意图。图4系本发明多工序流程式产品生产排程方法一第一较佳实施例的有向网络模型示意图。图5系本发明多工序流程式产品生产排程方法一第一较佳实施例的最佳人力配置有向网络模型示意图。【具体实施方式】有鉴于现有的产品生产排程方法的计算量庞大，难以在实际执行上根据每天的人力总数及工序变动在有限时间内获得符合效率标准的工序合并及人力配置排程，本发明提供一种多工序流程式产品生产排程方法，由一生产排程应用程序执行，能大幅降低获得最佳配置所需之计算次数，使得计算机能够快实时根据当日人力总数及工序计算获得最佳配置。请参阅图1所示，该产品生产排程方法包含以下步骤：接收一产品种类信息，根据产品种类信息读取一产品基础信息数据库，该产品基础信息数据库包含一工序序号信息，以及对应该工序序号信息的一工序周期时间信息、一工序种类信息(s101)；根据该工序序号信息及该工序种类信息产生一有向网络模型(s102)；根据该有向网络模型产生一组流量限制式(s103)；接收一人力数量信息，根据该人力数量信息产生一人力限制式(s104)；读取一目标函示，并根据该组流量限制式、工序周期时间信息，计算该目标函式基于该有向网络模型之一最佳解，且输出对应该最佳解的一人力配置(s105)。该人力数量信息包含到职的总人力数，该工序序号信息包含复数工序序号，每一工序序号依序对应该产品的其中一工序，该工序种类信息包含各该工序序号对应的工序种类，工序周期时间信息包含各该工序序号对应的一周期时间，也就是该产品通过并完成该工序所需的一平均时间。为了详细说明本发明的多工序流程式生产排程方法，先说明一产品的生产流程中的各该变量。其中，到职的总人力数为q人，工序种类有m个，且该产品总共有j1～jn共n道工序，各该工序ji分别属于m个工序种类中的其中一种，mk为第k类的工序之集合。平均一人执行一道工序ji并产生通过该工序之一件半成产品所需之一周期时间为pi，若为合并工序jij，所需之周期时间为pij。其中，工序ji～jj需属于同一种类工序且为相邻工序才能形成合并工序jij，也就是说，jij成立之条件为ji～jj∈mk。此外，较佳的，设定m1为手工工序种类之集合，而属于手工之工序可以与任何其他种类之工序进行合并，也就是说，jij成立之条件为ji～jj∈(mk∪m1)。在本发明中，通过生产排程方法产出一种人力配置，即代表在上述工序合并的条件限制下决定一种工序的合并方式，并且将当天之人力数量分配到各该工序或合并工序。以下条列出上述的各该变量及其定义：n：工序总数q：人力总数m：工序种类总数ji：第i工序；mk：第k种类工序之集合；jij：ji～jj的合并工序，i＝1～n，j＝1～n，i≤j；pi：第i工序的周期时间，代表平均一人执行该工序；pij：合并工序jij的周期时间，根据上述生产排程之变量，可衍伸出产能应变函式：ci：单人单站产能，第i工序ji的单人产能，其中t为单位时间，因此ci即为由1人执行该工序ji，在一单位时间内可以完成之产品件数；cij：合并工序jij的单人产能，在某一人力配置下，若该工序jij分配了多人同时进行，则该工序的产能与分配到的人数成正比，即该工序的产能为人数与单人产能的乘积。接下来说明本发明的生产排程方法之各该步骤说明。请参阅图2所示，为了将各该工序储存为该有向网络模型，根据该产品之工序序号，定义该有向网络模型中的节点集合：n＝{ai，bi}，i＝1～n；其中，ai、bi为一工序ji的转运节点；v＝{s，t}un，s为供给节点，即生产线之起点；t为需求节点，即生产线之终点。在本有向网络模型中，ai为工序ji的入站转运节点，bi为一工序ji的出站转运节点。请参阅图3所示，接着根据工序种类，定义该有向网络模型中的弧向量集合a＝a1∪a2∪a3∪a4，其中：a1＝{(s，a1)}；a2＝{(ai，bj)}，ai，bj∈n，j≥i；其中，当j＞i；弧(ai，bj)成立需考虑工序种类集合，也就是说，若弧(ai，bj)要成立，则ji，jj∈mk∪m1，k＝2，3，…m，且弧(ai x，bj x)都须成立，x＝1，2…，(j-i)；a3＝{(bi，ai 1)}，bi，ai 1∈n，i＝1，2，…，n-1；(bi，ai 1)成立表示其中一工序ji连接至下一工序ji 1；a4＝{(bn，t)}。接着，定义流量函式f(x，y)，并且定义f(u，v)∈{0，1}。f(x，y)＝1，表示有流量从x至y；f(x，y)＝0，表示没有流量从x至y，其中：f(s，a1)＝1，表示j1为供给起点后的第一道工序；f(bn，t)＝1，表示jn为需求终点前最后一道工序；f(ai，bj)＝1，且j＝i，表示安排ji工序为单独执行之工序；f(ai，bj)＝1，且j＞i，表示安排ji～jj为合并工序jij；f(bi，ai 1)＝1，表示安排ji工序结束之后连接jj工序。举例来说，以图3为例，在一人力配置中，当流量函式f(a1，b2)＝1，表示设定工序j1～j2合并为一道合并工序j12执行，当f(a3，b3)＝1，表示设定工序j3为单独执行之工序。此外，f(s，a1)及f(bn，t)皆预设为1，确保生产程序之开始进入第一道工序与最后一道工序之结束。接着定义人力函式w(ai，bj)。w(ai，bj)为工序jij所配置之人力数，符合即，各该工序的人力数和为人力总数。举例来说，当f(a1，b2)＝1，且w(ai，bj)＝5，表示合并工序j12分配5人进行该合并工序。根据上述流量及人力函数定义，可进一步确认单一工序的产能为该工序的单人产能与该站配置之人力数的乘积，即：进一步的，一生产线产出之完成产品数量受到在该特定人力配置下，具有最低产能之该工序的限制。也就是说，该生产线产生之完成产品数量等同于具有最低产能的该工序的产生之产品件数。根据上述原因，可订定该人力配置的人均效率(poh)为在该人力配置下，具有最低单站产能的该工序的之单站产能除以当天人力总数，也就是在一单位时间内，平均一人产生之完成产品件数。此外，在判断上述最低单站产能时，也必须考虑该工序或该合并工序是否有被选择。在计算中，若该工序或该合并工序根本没有在该人力配置中被选择，该工序对应的流量函式值f(ai，bj)＝0，使得其对应的单站产能为0，则会导致该工序被判断为具有最低单站产能，然而此状况是一不合理的配置，不应出现在任何可执行的人力配置中。为避免上述可能瑕疵，在本发明中，进一步定义一单站产能函式c(f(ai，bj)，w(ai，bj))：其中，α为一异常警示常数，较佳为选择一极大的数，c(f(ai，bj)，w(ai，bj))即为该人力配置下的单站产能函式。因此，可以将该人力配置的人均效率poh表示为：接下来定义一目标函式，即最佳的人均效率max(poh)。由上述人均效率poh之定义式可知，将最佳人均效率可列为：此外，在一较佳实施例中，为了避免流量函式值为1，而人力函式值为0的配置产生的情形发生，也就是为了避免安排了其中一工序或合并工序，却没有分配人力的无法实施错误情形发生，进一步产生一个收敛函式：其中，定义当f(ai，bj)＝1，但w(ai，bj)＝0时，m(ai，bj)＝1。即：而进一步的，藉由上述收敛函式，还将代表目标函式的最佳人均效率修正为：上述修正过的目标函式使得在运算某一人力配置的人均效率时，若发生f(ai，bj)＝1，但w(ai，bj)＝0的不合理配置，则：m(ai，bj)＝1也就是说，修正过的目标函式使得包含有f(ai，bj)＝1且w(ai，bj)＝0的不合理人力分配的不可能为一最大值。如此一来，即达到避免该包含有不合理人力分配的人力配置根据运算结果被选择为最佳人力配置的目的。在该有向网络模型中，设定由供给起点s进入第一工序j1的输入流量为1，以及由最后一到工序jn进入需求终点t的输出流量为1，且根据各该转运节点的输入流量ai、bj必须等于输出流量之限制，可得到以下流量限制式：对a1而言：对ai而言：对bj而言：对bn而言：根据输入的一人力数量信息，判断当天人力总数为当日出勤人数q，可以得到人力限制式：最后，根据上述有向网络模型，及据以产生的流量限制式及人力限制式，通过软件之整数规划求解算法，计算上述目标函式max(poh)之一最佳解，并且输出对应该最佳解的流量函式值及人力函式值，也就是输出该最佳人力配置下的工序合并方法及人力分配方法。以下将进一步举例说明本发明产品生产排程方法之运作方法。举例而言，当天要生产之产品为袜子，因此管理人员输入生产排程应用程序的一产品种类信息包含袜子产品之代表信息，例如为一产品代码。该生产排程应用程序根据该产品种类信息读取一产品基础信息数据库。袜子的产品基础信息数据库如下表表1所示。工序序号(i)工序描述周期时间(pi)工序种类工序种类编号(k)1袜套布标车缝10.2s计算机平车22袜套缝合3.4s八针车33剪八针头5.7s手工14翻袜套2.9s手工1表1该产品基础信息数据库包含袜子产品生产线中各工序之工序序号、工序周期时间及工序种类及其编号列。根据上表，得知当天该产品之生产线的各该变量如下：工序总数n＝4；工序种类集合：m1＝{j3，j4}、m2＝{j1}、m3＝{j2}。其中，该第3工序j3及该第4工序j4为手工工序，而第1工序j1及第2工序j2为不同种类之车缝工序。也就是说，根据相同种类工序可合并，以及手工工序可与任何其他种类工序合并之条件，可安排的工序合并方式例如为第2、3工序合并为j23、第3、4工序合并为j34、第2～4工序合并为j24等。请一并参阅图4所示，图4为根据上述工序相关信息建立之有向网络模型。首先根据工序总数为4之信息，产生以下节点集合：转运节点集合n＝{a1，a2，a3，a4，b1，b2，b3，b4}；v＝{s，t}∪n＝{s，t，a1，a2，a3，a4，b1，b2，b3，b4}。接着定义弧向量集合a＝a1∪a2∪a3∪a4，其中：a1＝{(s，a1)}；a2＝{(a1，b1)，(a2，b2)，(a2，b3)，(a2，b4)，(a3，b3)，(a4，b4)，(a3，b4)}；a3＝{(b1，a2)，(b2，a3)，(b3，a4)}；a4＝{(b4，t)}。产生该有向网络模型后，进一步根据该弧向量集合，则可以产生以下流量函式：f(s，a1)、f(a1，b1)、f(α2，b2)、f(a2，b3)、f(a2，b4)、f(a3，b3)、f(a4，b4)、f(a3，b4)、f(b1，a2)、f(b2，a3)、f(b3，a4)、f(b4，t)。根据上述流量函式，产生以下流量限制式：对a1而言：f(s，a1)＝f(a1，b1)＝1；对a2而言：f(b1，a2)＝f(a2，b2) f(a2，b3) f(a2，b3) f(a2，b4)；对a3而言：f(b2，a3)＝f(a3，b3) f(a3，b4)；对a4而言：f(b3，a4)＝f(a4，b4)；对b1而言：f(a1，b1)＝f(b1，a2)；对b2而言：f(a2，b2)＝f(a2，b3)；对b3而言：f(a2，b3) f(a3，b3)＝f(b3，a4)；对b4而言：f(a2，b4) f(a3，b4) f(a4，b4)＝f(b4，t)＝1。而考虑人力分配的单站产能函式如下：以及产生避免安排错误的收敛函式m(ai，bj)：进一步的，生产排程应用程序接收由管理人员输入的人力数量信息，例如当天到职人数为10，则人力数量信息中的人力总数q＝10，因此具以产生人力限制式：即代表各该工序或合并工序所分配到的人力数的总和为当天人力总数。根据该有向网络模型中及之上述的流量函式及人力函式，可产生一待运算之人力配置表，如下表2所示。表2在最后一步骤中，根据该目标函式max(poh)，且在上述流量限制式及人力限制式的限制条件下，通过规划求解之算法，得到具有最高的最低单站产能的最佳解的人力配置如下表表3所示，其中，流量函式值及代表工序合并方式，人力函式值则代表人力数量分配。其中，设定单位时间t为1小时，即3600秒，因此该单人单站产能及单站产能系以3600产出之产品件数表示。表3请一并参阅图5及表3所示，该产品生产的最佳人力配置为工序j2～j4合并为一合并工序j24，而在第1工序j1分配5人，该合并工序j24分配5人。在此人力配置下，该合并工序j24具有所有工序中之最低单站产能，即1500件。也就是说，该生产线在此最佳人力配置下，1小时产出1500件完成品产品。在上述的举例说明中，通过根据该有向网络模型及其流量限制式的规划求解运算，本实施例的产品生产排程方法仅需计算具有9条限制式的规划求解1次，获得该最佳人力配置。若通过习知的排列组合穷举法，则需运算35次。也就是说，本发明的计算复杂度将依据限制式数量影响计算时间，而限制式的数量必定小于不受人力q的影响，仅受工序数量n影响，因此使此问题能够在有限时间内求解。由此可知，本发明的产品生产排程方法大幅降低运算量，解决在有限时间内无法通过穷举法获得最佳人力配置之问题。以上所述仅是本发明的较佳实施例而已，并非对本发明做任何形式上的限制，虽然本发明已以较佳实施例揭露如上，然而并非用以限定本发明，任何熟悉本专业的技术人员，在不脱离本发明技术方案的范围内，当可利用上述揭示的技术内容做出些许更动或修饰为等同变化的等效实施例，但凡是未脱离本发明技术方案的内容，依据本发明的技术实质对以上实施例所作的任何简单修改、等同变化与修饰，均仍属于本发明技术方案的范围内。当前第1页1 2 3
技术特征：1.一种多工序流程式产品生产排程方法，由一生产排程应用程序执行，包含以下步骤：
接收一产品种类信息，根据产品种类信息读取一产品基础信息数据库，该产品基础信息数据库包含一工序序号信息，以及对应该工序序号信息的一工序周期时间信息、一工序种类信息；
根据该工序序号信息及该工序种类信息产生一有向网络模型；
根据该有向网络模型产生一组流量限制式；
接收一人力数量信息，根据该人力数量信息产生一人力限制式；
读取一目标函式，并根据该组流量限制式、该人力限制式及该工序周期时间信息，计算该目标函式基于该有向网络模型之一最佳解，且输出对应该最佳解的一人力配置。
2.如权利要求1所述之多工序流程式产品生产排程方法，其中，根据该工序序号信息及该工序种类信息产生一有向网络模型的步骤中，系包含以下步骤，
产生一转运节点集合及一弧向量集合；其中，
该有向网络模型包含该转运节点集合及该弧向量集合，
且该转运节点集合系包含复数入站转运节点及复数出站转运节点，且该工序序号信息中的一工序序号对应其中一入站转运节点及其中一出站转运节点；
该弧向量集合系包含根据转节点集合及工序种类信息产生的复数弧向量。
3.如权利要求2所述之多工序流程式产品生产排程方法，其中，根据该有向网络模型产生一组流量限制式的步骤中，包含
产生复数流量函式，各该流量函式对应其中一弧向量；
根据各该入站转运节点及各该出站转运节点的一输入流量等于一输出流量的限制规则，产生针对各该流量函式的该组流量限制式。
4.如权利要求1所述之多工序流程式产品生产排程方法，其中，读取一目标函式，并根据该组流量限制式、工序周期时间信息，计算该目标函式基于该有向网络模型之一最佳解的步骤中，系通过规划求解算法计算该最佳解。
5.如权利要求1所述之多工序流程式产品生产排程方法，其中，接收一人力数量信息，根据该人力数量信息产生一人力限制式的步骤，系包含以下步骤：
产生复数人力函式，各该人力函式对应其中一弧向量；
根据各该工序及合并工序的人力数和等于一人力总数的限制规则，产生各该人力函式值的合等于该人力数量信息的人力限制式。
6.如权利要求5所述之多工序流程式产品生产排程方法，其中，该人力限制式如下所示：
其中，ai为对应其中一工序序号i的入站转运节点，bj为对应其中一工序序号j的出站转运节点，w(ai，bj)为由一入站转运节点ai至一出站转运节点bj之人力分配数量，q为该人力总数。
7.如权利要求3所述之多工序流程式产品生产排程方法，其中，该组流量限制式如下所示：
a1：
ai：
bj：其中，
ai为对应其中一工序序号i的入站转运节点，bj为对应其中一工序序号j的出站转运节点，f(ai，bj)为由一入站转运节点ai至一出站转运节点bj的一流量函式，a为所有弧向量集合。
8.如权利要求7所述之多工序流程式产品生产排程方法，进一步包含以下步骤：
产生复数单站产能函式；单站产能函是如下所示：
其中，w(aι，bj)为由入站转运节点ai至出站转运节点bj的一人力函式，cij为根据该工序周期时间信息产生的一单人单站产能，α为一异常警示常数，a2为根据所有入站转运节点ai至出站转运节点bj定义的弧向量集合。
9.如权利要求8所述之多工序流程式产品生产排程方法，其中，该目标函式如下所示：
其中，
q为该人力数量信息包含的一人力总数。
10.如权利要求8所述之多工序流程式产品生产排程方法，其中，该目标函式如下所示：
其中，q为该人力数量信息包含的一人力总数，m(aι，bj)为一收敛函式，该收敛函式如下所示：
技术总结本发明的产品生产排程方法由一产品排程应用程序执行，系先接收一产品种类信息并据以读取包含工序序号信息、工序种类信息，根据工序序号信息、工序种类信息产生一有向网络模型，并且根据生产线的顺序产生一组流量限制式；接收一人力数量信息并据以产生一人力限制式；读取一有关最佳产能的目标函式，并且根据组流量限制式、人力限制式及工序周期时间信息计算目标函式的一最佳解及对应的人力配置；通过产生有向网络模型及对应的有限数量的流量限制式，大幅降低所需进行的运算次数，使得产品排成应用程序执行能在有限时间中获得最佳人力配置。
技术研发人员：许新居;陈科甫
受保护的技术使用者：威保控股股份有限公司
技术研发日：2019.09.12
技术公布日：2021.03.12
