TWI727425B

TWI727425B - 多工序流程式產品生產排程方法

Info

Publication number: TWI727425B
Application number: TW108133848A
Authority: TW
Inventors: 許新居; 陳科甫
Original assignee: 威保控股股份有限公司
Priority date: 2019-09-19
Filing date: 2019-09-19
Publication date: 2021-05-11
Also published as: TW202113701A

Abstract

本發明的產品生產排程方法由一產品排程應用程式執行，係先接收一產品種類資訊並據以讀取包含工序序號資訊、工序種類資訊，根據工序序號資訊、工序種類資訊產生一有向網路模型，並且根據生產線的順序產生一組流量限制式；接收一人力數量資訊並據以產生一人力限制式；讀取一有關最佳產能的目標函式，並且根據組流量限制式、人力限制式及工序週期時間資訊計算目標函式的一最佳解及對應的人力配置；通過產生有向網路模型及對應的有限數量的流量限制式，大幅降低所需進行的運算次數，使得產品排成應用程式執行能在有限時間中獲得最佳人力配置。

Description

多工序流程式產品生產排程方法

一種排程方法，尤指一種多工序流程式產品生產排程方法。

在紡織、製鞋等人力密集的產業中，一種產品的生產組裝作業中包含多道工序，並且使用大量的人力組成連續的生產線進行產品由原料到成品的加工及組裝。為了達到良好的生產效率，如何將人力適當的分配到各道工序中，便是每一個工廠在生產產品時必然面臨的問題。在進行人力分配的過程中，還需考慮生產線中各該工序之間的條件及相對關係。舉例來說，每一道工序所需的平均時間不相同，即相同人力在固定時間內進行每一道工序的效率不同。一般來說，一個工廠的生產效率定義為在固定時間內產出之完成品數量，而一件完成品的產出必須完整的通過所有工序。因此，完成品的數量受限於產能最低的該道工序的產出數量。換句話說，為了達到最佳的生產效率，各該工序的人力分配必須提高各道工序中產出數量最低的該道工序的產出數量，以提高完成品的產出數量。舉例來說，一生產線在當天的人力配置下，其中第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人，通過上述窮舉方法獲得最佳配置之計算量是任何一般電腦皆無法在每日開工前的有限時間得到該較佳配置。綜上所述，現有的生產排程方法勢必須進行進一步改良。

有鑑於現有的產品生產排程方法的計算量龐大，難以在實際執行上根據每天的人力數量及工序變動在有限時間內獲得符合效率標準的工序合併及人力分配排程，本發明提供一種多工序流程式產品生產排程方法，由一生產排程應用程式執行。該產品生產排程方法包含以下步驟：接收一產品種類資訊，根據產品種類資訊讀取一產品基礎資訊資料庫，該產品基礎資訊資料庫包含一工序序號資訊，以及對應該工序序號資訊的一工序週期時間資訊、一工序種類資訊；根據該工序序號資訊及該工序種類資訊產生一有向網路模型；根據該有向網路模型產生一組流量限制式；接收一人力數量資訊，根據該人力數量資訊產生一人力限制式；讀取一目標函式，並根據該組流量限制式、工序週期時間資訊，計算該目標函式基於該有向網路模型之一最佳解，且輸出對應該最佳解的一人力配置。

該有向網路模型係根據該工序序號及對應的工序種類產生，而根據有向網路模型產生之該組流量限制式的數量受限於工序序號的數量，且不受人力數量的影響。通過根據有向網路模型及生產線順序限制產生的有限的限制式，大幅降低獲得最佳配置所需之計算次數，使得電腦能夠即時根據當日人力及工序計算獲得最佳配置。

J₁:第一工序

J₂:第二工序

J₃:第三工序

J_n:第n工序

J₂₄:第二工序至第四工序的合併工序

圖1係本發明多工序流程式產品生產排程方法的流程示意圖。

圖2係本發明多工序流程式產品生產排程方法的一有向網路模型的轉運節點示意圖。

圖3係本發明多工序流程式產品生產排程方法的一有向網路模型示意圖。

圖4係本發明多工序流程式產品生產排程方法一第一較佳實施例的有向網路模型示意圖。

圖5係本發明多工序流程式產品生產排程方法一第一較佳實施例的最佳人力配置有向網路模型示意圖。

有鑑於現有的產品生產排程方法的計算量龐大，難以在實際執行上根據每天的人力總數及工序變動在有限時間內獲得符合效率標準的工序合併及人力配置排程，本發明提供一種多工序流程式產品生產排程方法，由一生產排程應用程式執行，能大幅降低獲得最佳配置所需之計算次數，使得電腦能夠快即時根據當日人力總數及工序計算獲得最佳配置。

請參閱圖1所示，該產品生產排程方法包含以下步驟：接收一產品種類資訊，根據產品種類資訊讀取一產品基礎資訊資料庫，該產品基礎資訊資料庫包含一工序序號資訊，以及對應該工序序號資訊的一工序週期時間資訊、一工序種類資訊(S101)；根據該工序序號資訊及該工序種類資訊產生一有向網路模型(S102)；根據該有向網路模型產生一組流量限制式(S103)；接收一人力數量資訊，根據該人力數量資訊產生一人力限制式(S104)；讀取一目標函示，並根據該組流量限制式、工序週期時間資訊，計算該目標函式基於該有向網路模型之一最佳解，且輸出對應該最佳解的一人力配置(S105)。

該人力數量資訊包含到職的總人力數，該工序序號資訊包含複數工序序號，每一工序序號依序對應該產品的其中一工序，該工序種類資訊包含各該工序序號對應的工序種類，工序週期時間資訊包含各該工序序號對應的一週期時間，也就是該產品通過並完成該工序所需的一平均時間。

為了詳細說明本發明的多工序流程式生產排程方法，先說明一產品的生產流程中的各該變數。其中，到職的總人力數為q人，工序種類有m個，且該產品總共有J₁~J_n共n道工序，各該工序J_i分別屬於m個工序種類中的其中一種，M_k為第k類的工序之集合。平均一人執行一道工序J_i並產生通過該工序之一件半成產品所需之一週期時間為P_i，若為合併工序J_ij，所需之週期時間為P_ij。其中，工序J_i~J_j需屬於同一種類工序且為相鄰工序才能形成合併工序J_ij，也就是說，J_ij成立之條件為J_i~J_j

M_k。此外，較佳的，設定M₁為手工工序種類之集合，而屬於手工之工序可以與任何其他種類之工序進行合併，也就是說，J_ij成立之條件為J_i~J_j

(M_k∪M₁)。

在本發明中，通過生產排程方法產出一種人力配置，即代表在上述工序合併的條件限制下決定一種工序的合併方式，並且將當天之人力數量分配到各該工序或合併工序。

以下條列出上述的各該變數及其定義：n：工序總數

q：人力總數

m：工序種類總數

J_i：第i工序；M_k：第k種類工序之集合；J_ij：J_i~J_j的合併工序，i=1~n，j=1~n，i≦j；P_i：第i工序的週期時間，代表平均一人執行該工序；P_ij：合併工序J_ij的週期時間，

，i≦j；根據上述生產排程之變數，可衍伸出產能應變函式： C_i：單人單站產能，第i工序J_i的單人產能，

，其中T為單位時間，因此C_i即為由1人執行該工序J_i，在一單位時間內可以完成之產品件數；C_ij：合併工序J_ij的單人產能，

；在某一人力配置下，若該工序J_ij分配了多人同時進行，則該工序的產能與分配到的人數成正比，即該工序的產能為人數與單人產能的乘積。

接下來說明本發明的生產排程方法之各該步驟說明。

請參閱圖2所示，為了將各該工序儲存為該有向網路模型，根據該產品之工序序號，定義該有向網路模型中的節點集合：N={a_i,b_i}，i=1~n；其中，a_i、b_i為一工序J_i的轉運節點；V={s,t}∪N，s為供給節點，即生產線之起點；t為需求節點，即生產線之終點。

在本有向網路模型中，a_i為工序J_i的入站轉運節點，b_i為一工序J_i的出站轉運節點。

請參閱圖3所示，接著根據工序種類，定義該有向網路模型中的弧向量集合A=A ₁∪A ₂∪A ₃∪A ₄，其中：A ₁={(s,a ₁)}；

,j

i備其中，當j>i；弧(a _i,b _j)成立需考量工序種類集合，也就是說，若弧(a_I,b_j)要成立，則J _I,J _j

M _k∪M ₁，k=2,3,…m，且弧(a _i+x,b _j)都須成立，x=1,2…,(j-i)；

,i=1,2,…,n-1；(b _i,a _i+1)成立表示其中一工序J_i連接至下一工序J_i+1；A ₄={(b _n,t)}。

接著，定義流量函式f(x,y)，並且定義f(u,v)

{0,1}。

f(x,y)=1，表示有流量從x至y；f(x,y)=0，表示沒有流量從x至y，其中：f(s,a₁)=1，表示J₁為供給起點後的第一道工序；f(b_n,t)=1，表示J_n為需求終點前最後一道工序；f(a_i,b_j)=1，且j=i，表示安排J_i工序為單獨執行之工序；f(a_i,b_j)=1，且j>i，表示安排J_i~J_j為合併工序J_ij； f(b_i,a_i+1)=1，表示安排J_i工序結束之後連接J_j工序。

舉例來說，以圖3為例，在一人力配置中，當流量函式f(a₁,b₂)=1，表示設定工序J₁~J₂合併為一道合併工序J₁₂執行，當f(a₃,b₃)=1，表示設定工序J₃為單獨執行之工序。此外，f(s,a₁)及f(b_n,t)皆預設為1，確保生產程序之開始進入第一道工序與最後一道工序之結束。

接著定義人力函式w(a_i,b_j)。w(a_i,b_j)為工序J_ij所配置之人力數，符合

，即，各該工序的人力數和為人力總數。舉例來說，當f(a₁,b₂)=1，且w(a_i,b_j)=5，表示合併工序J₁₂分配5人進行該合併工序。

根據上述流量及人力函式定義，可進一步確認單一工序的產能為該工序的單人產能與該站配置之人力數的乘積，即：

進一步的，一生產線產出之完成產品數量受到在該特定人力配置下，具有最低產能之該工序的限制。也就是說，該生產線產生之完成產品數量等同於具有最低產能的該工序的產生之產品件數。根據上述原因，可訂定該人力配置的人均效率(POH)為在該人力配置下，具有最低單站產能的該工序的之單站產能除以當天人力總數，也就是在一單位時間內，平均一人產生之完成產品件數。

此外，在判斷上述最低單站產能時，也必須考量該工序或該合併工序是否有被選擇。在計算中，若該工序或該合併工序根本沒有在該人力配置中被選擇，該工序對應的流量函式值f(a _i,b _j)=0，使得其對應的單站產能為0，則會導致該工序被判斷為具有最低單站產能，然而此狀況是一不合理的配置，不應出現在任何可執行的人力配置中。為避免上述可能瑕疵，在本發明中，進一步定義一單站產能函式C(f(a _i,b _j),w(a _i,b _j))：

其中，α為一異常警示常數，較佳為選擇一極大的數，C(f(a _i,b _j),w(a _i,b _j))即為該人力配置下的單站產能函式。

因此，可以將該人力配置的人均效率POH表示為：

接下來定義一目標函式，即最佳的人均效率Max(POH)。由上述人均效率POH之定義式可知，將最佳人均效率可列為：

此外，在一較佳實施例中，為了避免流量函式值為1，而人力函式值為0的配置產生的情形發生，也就是為了避免安排了其中一工序或合併工序，卻沒有分配人力的無法實施錯誤情形發生，進一步產生一個收斂函式：

m(a _i,b _j)。其中，定義當f(a _i,b _j)=1，但w(a _i,b _j)=0時，m(a _i,b _j)=1。即：

而進一步的，藉由上述收斂函式，還將代表目標函式的最佳人均效率修正為：

上述修正過的目標函式使得在運算某一人力配置的人均效率時，若發生f(a _i,b _j)=1，但w(a _i,b _j)=0的不合理配置，則：

也就是說，修正過的目標函式使得包含有f(a _i,b _j)=1且w(a _i,b _j)=0的不合理人力分配的POH-

m(a _i,b _j)不可能為一最大值。如此一來，即達到避免該包含有不合理人力分配的人力配置根據運算結果被選擇為最佳人力配置的目的。

在該有向網路模型中，設定由供給起點s進入第一工序J₁的輸入流量為1，以及由最後一到工序J_n進入需求終點t的輸出流量為1，且根據各該轉運節點的輸入流量a_i、b_j必須等於輸出流量之限制，可得到以下流量限制式：對a₁而言：

,j=1~n；對a_i而言：

,j

i；對b _j而言：

,j

i；對b _n而言：

。

根據輸入的一人力數量資訊，判斷當天人力總數為當日出勤人數q，可以得到人力限制式：

最後，根據上述有向網路模型，及據以產生的流量限制式及人力限制式，通過軟體之整數規劃求解演算法，計算上述目標函式Max(POH)之一最佳解，並且輸出對應該最佳解的流量函式值及人力函式值，也就是輸出該最佳人力配置下的工序合併方法及人力分配方法。

以下將進一步舉例說明本發明產品生產排程方法之運作方法。舉例而言，當天要生產之產品為襪子，因此管理人員輸入生產排程應用程式的一產品種類資訊包含襪子產品之代表資訊，例如為一產品代碼。該生產排程應用程式根據該產品種類資訊讀取一產品基礎資訊資料庫。襪子的產品基礎資訊資料庫如下表表1所示。

該產品基礎資訊資料庫包含襪子產品生產線中各工序之工序序號、工序週期時間及工序種類及其編號列。根據上表，得知當天該產品之生產線的各該變數如下：工序總數n=4；工序種類集合：M₁={J₃,J₄}、M₂={J₁}、M₃={J₂}。

其中，該第3工序J₃及該第4工序J₄為手工工序，而第1工序J₁及第2工序J₂為不同種類之車縫工序。也就是說，根據相同種類工序可合併，以及手工工序可與任何其他種類工序合併之條件，可安排的工序合併方式例如為第2、3工序合併為J₂₃、第3、4工序合併為J₃₄、第2~4工序合併為J₂₄等。

請一併參閱圖4所示，圖4為根據上述工序相關資訊建立之有向網路模型。首先根據工序總數為4之資訊，產生以下節點集合：轉運節點集合N={a ₁,a ₂,a ₃,a ₄,b ₁,b ₂,b ₃,b ₄}；V={s,t}∪N={s,t,a ₁,a ₂,a ₃,a ₄,b ₁,b ₂,b ₃,b ₄}。

接著定義弧向量集合A=A ₁∪A ₂∪A ₃∪A ₄，其中：A ₁={(s,a ₁)}；A ₂={(a ₁,b ₁),(a ₂,b ₂),(a ₂,b ₃),(a ₂,b ₄),(a ₃,b ₃),(a ₄,b ₄),(a ₃,b ₄)}；A ₃={(b ₁,a ₂),(b ₂,a ₃),(b ₃,a ₄)}；A ₄={(b ₄,t)}。

產生該有向網路模型後，進一步根據該弧向量集合，則可以產生以下流量函式：f(s,a ₁)、f(a ₁,b ₁)、f(a ₂,b ₂)、f(a ₂,b ₃)、f(a ₂,b ₄)、f(a ₃,b ₃)、f(a ₄,b ₄)、f(a ₃,b ₄)、f(b ₁,a ₂)、f(b ₂,a ₃)、f(b ₃,a ₄)、f(b ₄,t)。

根據上述流量函式，產生以下流量限制式：對a₁而言：f(s,a ₁)=f(a ₁,b ₁)=1；對a₂而言：f(b ₁,a ₂)=f(a ₂,b ₂)+f(a ₂,b ₃)+f(a ₂,b ₃)+f(a ₂,b ₄)；對a₃而言：f(b ₂,a ₃)=f(a ₃,b ₃)+f(a ₃,b ₄)；對a₄而言：f(b ₃,a ₄)=f(a ₄,b ₄)；對b₁而言：f(a ₁,b ₁)=f(b ₁,a ₂)；對b₂而言：f(a ₂,b ₂)=f(a ₂,b ₃)；對b₃而言：f(a ₂,b ₃)+f(a ₃,b ₃)=f(b ₃,a ₄)；對b₄而言：f(a ₂,b ₄)+f(a ₃,b ₄)+f(a ₄,b ₄)=f(b ₄,t)=1。

而考量人力分配的單站產能函式如下：

以及產生避免安排錯誤的收斂函式m(a _i,b _j)：

進一步的，生產排程應用程式接收由管理人員輸入的人力數量資訊，例如當天到職人數為10，則人力數量資訊中的人力總數q=10，因此具以產生人力限制式：

，即代表各該工序或合併工序所分配到的人力數的總和為當天人力總數。

根據該有向網路模型中及之上述的流量函式及人力函式，可產生一待運算之人力配置表，如下表2所示。

在最後一步驟中，根據該目標函式Max(POH)，且在上述流量限制式及人力限制式的限制條件下，通過規劃求解之演算法，得到具有最高的最低單站產能的最佳解的人力配置如下表表3所示，其中，流量函式值及代表工序合併方式，人力函式值則代表人力數量分配。其中，設定單位時間T為1小時，即3600秒，因此該單人單站產能及單站產能係以3600產出之產品件數表示。

請一併參閱圖5及表3所示，該產品生產的最佳人力配置為工序J₂~J₄合併為一合併工序J₂₄，而在第1工序J₁分配5人，該合併工序J₂₄分配5人。在此人力配置下，該合併工序J₂₄具有所有工序中之最低單站產能，即1500件。也就是說，該生產線在此最佳人力配置下，1小時產出1500件完成品產品。

在上述的舉例說明中，通過根據該有向網路模型及其流量限制式的規劃求解運算，本實施例的產品生產排程方法僅需計算具有9條限制式的規劃求解1次，獲得該最佳人力配置。若通過習知的排列組合窮舉法，則需運算35次。

也就是說，本發明的計算複雜度將依據限制式數量影響計算時間，而限制式的數量必定小於

，不受人力q的影響，僅受工序數量n影響，因此使此問題能夠在有限時間內求解。由此可知，本發明的產品生產排程方法大幅降低運算量，解決在有限時間內無法通過窮舉法獲得最佳人力配置之問題。

以上所述僅是本發明的較佳實施例而已，並非對本發明做任何形式上的限制，雖然本發明已以較佳實施例揭露如上，然而並非用以限定本發明，任何熟悉本專業的技術人員，在不脫離本發明技術方案的範圍內，當可利用上述揭示的技術內容做出些許更動或修飾為等同變化的等效實施例，但凡是未脫離本發明技術方案的內容，依據本發明的技術實質對以上實施例所作的任何簡單修改、等同變化與修飾，均仍屬於本發明技術方案的範圍內。

Claims

一種多工序流程式產品生產排程方法，由一生產排程應用程式執行，包含以下步驟：接收一產品種類資訊，根據產品種類資訊讀取一產品基礎資訊資料庫，該產品基礎資訊資料庫包含一工序序號資訊，以及對應該工序序號資訊的一工序週期時間資訊、一工序種類資訊；其中，該工序序號資訊包含複數工序序號，該工序種類資訊包含各該工序序號對應的工序種類；根據該工序序號資訊及該工序種類資訊產生一有向網路模型；其中，該有向網路模型包含一轉運節點集合及一弧向量集合，且該轉運節點集合係包含對應各該工序序號的複數入站轉運節點a _i及複數出站轉運節點b _j，其中i、j代表工序序號且為正整數；該弧向量集合係包含根據轉節點集合及工序種類資訊產生的複數弧向量，且其中包含由各該入站轉運節點a _i至各該出站轉運節點b _j之複數弧向量，且當j>i，弧向量(a _i,b _j)須在對應工序序號i至對應工序序號j之工序種類皆相同或為一手工工序種類時成立；根據該有向網路模型產生一組流量限制式；接收一人力數量資訊，根據該人力數量資訊產生一人力限制式；讀取一目標函式，並根據該組流量限制式、該人力限制式及該工序週期時間資訊，計算該目標函式基於該有向網路模型之一最佳解，且輸出對應該最佳解的一人力配置。
如請求項1所述之多工序流程式產品生產排程方法，其中，根據該有向網路模型產生一組流量限制式的步驟中，包含產生複數流量函式，各該流量函式對應其中一弧向量；根據各該入站轉運節點及各該出站轉運節點的一輸入流量等於一輸出流量的限制規則，產生針對各該流量函式的該組流量限制式。
如請求項1所述之多工序流程式產品生產排程方法，其中，讀取一目標函式，並根據該組流量限制式、工序週期時間資訊，計算該目標函式基於該有向網路模型之一最佳解的步驟中，係通過規劃求解演算法計算該最佳解。
如請求項1所述之多工序流程式產品生產排程方法，其中，接收一人力數量資訊，根據該人力數量資訊產生一人力限制式的步驟，係包含以下步驟：產生複數人力函式，各該人力函式對應其中一弧向量；根據各該工序及合併工序的人力數和等於一人力總數的限制規則，產生各該人力函式值的合等於該人力數量資訊的人力限制式。
如請求項4所述之多工序流程式產品生產排程方法，其中，該人力限制式如下所示：
其中，w(a_i,b_j)為由入站轉運節點a_i至出站轉運節點b_j之人力分配數量，q為該人力總數，A為弧向量集合，f(a _i,b _j)為由入站轉運節點a_i至出站轉運節點b_j的一流量函式且f(a _i,b _j)
{0,1}。
如請求項2所述之多工序流程式產品生產排程方法，其中，該組流量限制式如下所示：a ₁：
,j=1~n；a _i：
,2
i
n,j
i；b _j：
,j
i；其中，f(a_i,b_j)為由入站轉運節點a_i至出站轉運節點b_j的一流量函式，A為所有弧向量集合。
如請求項6所述之多工序流程式產品生產排程方法，進一步包含以下步驟：產生複數單站產能函式；單站產能函式如下所示：
其中，w(a_i,b_j)為由入站轉運節點a_i至出站轉運節點b_j的一人力函式，C_ij為根據該工序週期時間資訊產生的一單人單站產能，α為一異常警示常數，A₂為根據所有入站轉運節點a_i至出站轉運節點b_j定義的弧向量集合。
如請求項7所述之多工序流程式產品生產排程方法，其中，該目標函式如下所示：
；其中，q為該人力數量資訊包含的一人力總數。
如請求項7所述之多工序流程式產品生產排程方法，其中，該目標函式如下所示：
其中，q為該人力數量資訊包含的一人力總數，m(a _i,b _j)為一收斂函式，該收斂函式如下所示：
,(a _i,b _j)
A ₂。