零工型工廠以工作為導向的啟發式排程系統之構建

摘要

　　由1990年 Hastings and Yeh 所作之研究結果顯示，以工作為導向的啟發式 (Job Oriented Heuristic；簡稱JOH) 排程系統，在解實際業界生產排程之問題時，可以得到很好的排程績效。JOH排程法每次只考量一個工作的排程規劃，必定排完一個工作之所有加工作業後，才會去排下一個工作。此外，系統能滿足個別工作之不同排程需求。為擴展系統之適用性，目前發展出許多JOH排程程序，例如：混合排程法 (Hybrid Scheduling) 、最小處理時間 (Minimum in Process Time；簡稱MIPT) 法則、作業分割 (Operation Splitting) 程序與部份排程法 (Partial Scheduling) 等等，但在實作上，卻沒有深入探討如何使用這些排程方法，以排出不錯的初始排程計畫。因此，本研究首先探討JOH排程系統之理論與方法，其次，探討如何針對不同性質的工作，選取前推排程方法 (Forward Scheduling) 或是後推排程方法 (Backward Scheduling) ，並結合MIPT法則與作業分割程序之優點，發展出一套JOH排程之演算法，以滿足工作不同之需求，並產生有效可行的排程結果，最後並以一範例來說明所提方法之可行性。

　　在經濟環境、科技技術瞬息萬變的衝擊下，加上顧客對於產品多樣化的需求與苛求型態，產業界在面臨此成本要低、品質要好、交期要短及產品要安全之激烈競爭環境時，必需擬定立於不敗之地的經營策略，以圖公司之永續經營。由於零工型 (Job Shop) 生產製造環境中的情況極為複雜，要尋求最佳生產排程計畫，更是困難。然而，由過去學者 (Baker and McMahon 1985, Lageweg et al. 1977, Lawler et al. 1982) 所做研究結果顯示，以啟發式程序來解實際生產排程問題，是唯一可行的方法。在1990年Hastings and Yeh 根據其多年實務經驗，所歸納出以工作為導向的啟發式程序 (Job-Oriented Heuristics, JOH) 之眾多優點，使本研究相信，工業界若採取JOH排程系統，將能有效又快速地得到良好的生產排程計畫。

　　為了擴展JOH排程系統的適用性，目前發展出許多JOH排程程序，例如：混合排程法可以在短期內保持機器的忙碌性，但卻可避免Long Due-Date Job過早完成作業；而作業分割程序可使加工作業儘早完成，以避免延遲的風險；至於MIPT排程法則可以使整個工作的處理時間最小化，以降低在製品的庫存；其它尚有部份排程法、單一工作排程法等，這些程序讓生管人員可以有效地管理大規模的生產排程問題，包括交期、緊急訂單、滿足顧客需求及估價單遞送日期等問題。所以，本研究主要在探討以工作為導向的啟發式 (JOH) 排程系統之理論與方法，並針對不同工作之需求，採取適當的排程方法與策略，以發展出一套有效可行的JOH生產排程演算法。

　　以工作為導向之啟發式排程法 (JOH) 的運作方式，是根據工作的優先順序，每次挑選優先順序最高的工作，經由排程方法來決定工作之各加工作業的加工起迄時間，排完後才會挑選下一個工作來排。所以以工作為導向之啟發式排程法 (JOH) 是每次以一個工作之所有加工作業來考量。在 1982 年 Hastings et al. 提出了以工作為導向之前推排程法 (Forward Scheduling)，前推排程法的演算邏輯是從排程開始日起，選擇優序工作，前推每個加工作業在機器上之最早可加工時間，其特色為使資源的使用率提高及產生較緊密的排程 (Tight Schedule)。此方法一般適用於緊急訂單 (Rush Orders)、交期短的訂單 (Short Due-Date Order) 或者是低庫存成本的訂單 (Low Inventory Value Order) ，亦能用於發現可行的最早完工時間是否能符合顧客的交期要求。生管人員一般認為此方法是短期中使資源使用率提高的重要方法之一。

　　在 1983 年 White 和 Hastings 提出了以工作為導向之後推排程法 (Backward Scheduling)，後推排程法的演算邏輯是從訂單交貨日 (Order Due-Date) 起，選擇優序工作，後推每個加工作業在機器上之最遲可加工時間，其特色為準時的完成工作及產生較鬆散的排程 (Loose Schedule)。此方法一般適用於交期較長的訂單 (Long Due-Date Order) 或者是高庫存成本的訂單 (High Inventory Value Order) 。當組裝產品時所需要的零組件間，其所需要的總加工時間差異極大時，採用此方法則較採前推排程法適當，因為前推排程法會造成部份零組件等候時間的增加。而且在短期中，生管人員有時候也情願讓資源作適度的維修保養。

　　White (1986) 使用實驗設計法去比較以工作為導向之啟發式排程法 (JOH) 與以作業為導向之啟發式排程法 (Operation-Oriented Heuristics, OOH) 的整體績效，實驗結果顯示，就整體排程規劃的品質而言，以工作為導向之啟發式排程法 (JOH) 會優於一般常用的六種派工法則，因為以工作為導向之啟發式排程法可以花較少的時間產生較佳的排程結果。

　　Hastings and Yeh (1990) 依據他們在幾家工廠多年的排程經驗，歸納出幾項以工作為導向之啟發式排程法 (JOH) 的優點：(1) 生產人員易於瞭解、控制每張訂單之生產狀態；(2) 排程計算較有效率；(3) 可簡易的應付訂單優先順序之改變、重作 (Rework) 或缺料等狀況之發生；(4) 適用於有作業先後順序限制 (Precedence Constraints) 之訂單的生產排程。所以當加工現場的工作狀態改變時，以工作為導向之啟發式排程法 (JOH) 可以隨系統狀態改變而快速地更動排程 (Rescheduling)，而且只要作局部變動，不用像以作業為導向之啟發式排程法 (OOH) 需更動整個排程。

　　混合排程法 (Hybrid Scheduling Method) 乃結合前推有限產能排程法 (Forward Finite Capacity Scheduling) 及後推有限產能排程法 (Backward Finite Capacity Scheduling) 的優點，以工作為導向 (Job-Oriented) 之排程方法，此法之基本觀念為以整個工作或工令為排程單位，一次排一整個工作，排完後再繼續排下一個工作。混合排程交期設定法包含下面四個階段：(1) 根據某些準則 (如派工法則) 排序所有工作或工令；(2) 若有加工先後順序之技術限制 (如物料表，Bill of Material)，則依要求調整工作之排序；(3) 一次排 (加∕插) 一個工令到已排好之局部排程上，不可以干擾到已排好之工令；(4) 若完工時間超過交期 (前推排程) 或加工作業開始時間排到零基點以前 (後推排程) ，則修正局部排程，直到工作能被接受或拒單。其演算方式如下：『對工作之部份加工作業採前推有限產能排程法，部份加工作業採後推有限產能排程法，然後求出訂單之交貨日期、發放日期及訂單之最低在製時間 (Minimum-In-Process-Time, MIPT)。』

　　混合排程法之基本架構如圖三所示，其運作步驟如下：(1) 首先以前推排程法或後推排程法產生工作之細部排程；(2) 以後推排程法或前推排程法尋找核心作業 (Core Operation)，核心作業的定義為加工作業之開始加工時間不等於前一加工作業之完工時間 (後推尋找) 或者加工作業之完工時間不等於下一個加工作業之開始加工時間 (前推尋找)；(3) 以核心作業為標竿，然後將工作前置區段之加工作業作後推有限產能排程，求出工件之發放時間，或將工作後置區段之加工作業作前推有限產能排程，求出工件之完工時間。若有加工作業被後推至零基點以前，則對其採取加班、外包、分散負荷 (Offload)、作業分批 (Operation Splitting)、工作重疊 (Operation Overlapping) 等應變措施。

　　現以二個案例說明如何應用混合排程法求取最低之在製時間。第一案例如圖四(a) 所示，是使用前推排程法所產生之細部排程，其中工件 H 有三個加工作業 (H1, H2, H3)，由於 H2 加工作業之開始加工時間不等於 H1 加工作業之完工時間 (後推尋找)，所以選 H2 加工作業為核心作業。以 H2 加工作業為標竿，將 H2 加工作業前置區段之加工作業 H1 作後推有限產能排程，求出 H 工件之發放時間，結果如圖四(b) 所示。

　　另一案例說明如圖四(c) 所示，是使用後推排程法所產生之細部排程，其中工件 J 有三個加工作業 (J1, J2, J3)，交期為 8。由於 J2 加工作業之完工時間不等於 J3 加工作業之開工時間 (前推尋找)，所以選 J2 加工作業為核心作業。以 J2 加工作業為標竿，將 J2 加工作業後置區段之加工作業 J3 作前推有限產能排程，求出 J 工件之完工時間，排程結果如圖四(d) 所示。

　　為滿足工作需求，對於緊急工作、交期較近或有較低單位庫存成本的工作，應採取前推法去規劃生產排程；而對於交期較久或具有較高單位庫存成本的工作，則應採取後推排程法去做規劃。基於考量高資源使用率，與低庫存持有成本間的潛在目標衝突，本研究發展出一套適用於前推法與後推法的JOH排程演算法。其作法可分為四個步驟，首先從工作佇列中挑選優先順序最高的工作，再根據工作製程及機器相關資料，規劃出初始排程計畫，在初步規劃階段中，適時採用作業分割程序，以避免工作延遲的危險，並可提高資源使用率，接著採用MIPT法則調整每個工作的初始排程結果，以使整個工作的處理時間最小化，最後才檢測工作佇列中，是否還有工作需要做排程規劃。本演算法進行程序如下：(1) 初始排程產生階段。(2) MIPT法則調整階段。

　　本階段主要工作是利用前推排程法，找出每個Job之最早完成加工的時間點；或利用後推排程法找出每個Job之最晚需開始加工的時間點。其作法是從排程開始日前推或從交期日後推搜尋機器的可加工作業時間區段狀況，若有足夠的時間區段，則將作業排入，否則，將連續搜尋機器的可加工作業時間區段，直至最後有連續兩個時間區段足以排入作業時，才採取作業分割程序以將作業排入，等到工作之所有作業加工時間表皆已排完時，才進行下個階段。此階段之演算步驟如下：

　　MIPT法則的精神，在於縮短一件工作 (Job) 的作業間，或一群組裝工作的工作間之機器不必要的閒置時間 (Idle Time)，使整個工作的處理時間最小化，以降低工作廠現場的在製品庫存。而本研究所發展之JOH排程演算法，其第一個階段是採用後推法或前推法，結合MIPT法則的精神，調整第一個階段所產生的初始排程計畫。其作法，是依據核心作業，以調整其它作業，使其盡可能僅靠著核心作業，直至所有作業調整完。核心作業的定義，依使用後推法或前推法做排程調整的不同，而有以下兩種定義：(1) 使用後推法做調整，作業開始加工時間不等於前一個作業完成加工時間的作業，稱之為核心作業 (Core Operation)；而前一個作業則稱之為關鍵作業。(2) 使用前推法做調整，作業完成加工時間不等於下一個作業開始加工時間的作業，稱之為核心作業；而下一個作業則稱之為關鍵作業。MIPT法則調整階段之演算步驟如下：

　　現以實例說明，如何應用上述所發展的演算法，以前推排程法規劃出不錯的生產排程計畫。在實例中，假設目前在工作佇列上有八個工件需要加工，且已排好工作的優先順序如下：Job1、Job2、Job3、Job4、Job5、Job6、Job7、Job8。表一至表八是表每個Job的作業流程。

作業步驟	作業編號	加工機器	處理時間
1	O1,1	M1	6 min.
2	O1,2	M2	9 min.
3	O1,3	M3	7 min.

作業步驟	作業編號	加工機器	處理時間
1	O2,1	M1	5 min.
2	O2,2	M3	4 min.
3	O2,3	M2	7 min.
4	O2,4	M5	3 min.
5	O2,5	M4	5 min.

作業步驟	作業編號	加工機器	處理時間
1	O3,1	M2	2 min.
2	O3,2	M4	5 min.
3	O3,3	M1	8 min.
4	O3,4	M3	3 min.
5	O3,5	M5	4 min.

作業步驟	作業編號	加工機器	處理時間
1	O4,1	M4	7 min.
2	O4,2	M2	6 min.
3	O4,3	M5	3 min.
4	O4,4	M1	8 min.
5	O4,5	M3	3 min.

作業步驟	作業編號	加工機器	處理時間
1	O5,1	M3	3 min.
2	O5,2	M2	6 min.
3	O5,3	M1	9 min.
4	O5,4	M5	2 min.
5	O5,5	M4	4 min.

作業步驟	作業編號	加工機器	處理時間
1	O6,1	M5	5 min.
2	O6,2	M3	5 min.
3	O6,3	M1	8 min.
4	O6,4	M2	5 min.
5	O6,5	M4	6 min.

作業步驟	作業編號	加工機器	處理時間
1	O7,1	M5	5 min.
2	O7,2	M4	8 min.
3	O7,3	M3	7 min.
4	O7,4	M2	5 min.

作業步驟	作業編號	加工機器	處理時間
1	O8,1	M3	6 min.
2	O8,2	M2	7 min.
3	O8,3	M4	3 min.
4	O8,4	M1	3 min.
5	O8,5	M5	4 min.

　　本研究所發展之JOH排程演算法執行後，Job1和Job2在第一階段即已產生最佳排程結果，所以在第二階段，MIPT法則檢測到其工作處理時間已最小化後，就不再變動排程。接著進行Job3的排程規劃(圖五)，在第一階段之初始排程產生階段中，根據工作製程及機器相關資料，先從T0搜尋機器M2的可加工作業時間區段，檢測到機器M2的時段T0至T2是閒置的，於是將第一個作業O3,1排入，接著從T2搜尋機器M4的可加工作業時間區段，並在T11排入第三個坐作業O3,3，同理，將作業O3,5分別排入機器M3可加工作業時段T22~T25間與機器M5可加工作業時段T25~T29間，排完Job3的第五個作業後，即進行第二階段。在第二階段之MIPT法則調整階段中，從Job3之最早完成加工時間點T29，開始後推搜尋核心作業，直至判定作業O3,4為核心作業後(圖五)，才從T22後推搜尋關鍵作業O3,3的機器M1之可加工作業時間區段，並調整作業O3,3的排程時間為T14~T22 (圖六)，接著又檢測到作業O3,3亦為核心作業，故從T14後推搜尋關鍵作業O3,2的機器M4之可加作業時間區段，並調整作業O3,2的排程時間為T9~T14，同理，調整作業O3,1的排程時間，完成此階段序後，可使Job3的處理時間減少 4 分鐘。接著檢測工作佇列中，是否還有工作需要做作排程規劃。

　　同理，其餘Job的排程規劃，在第一階段中，可適時採用作業分割程序，以找出工作最早可完成時間。例如，在規劃Job7時 (如圖七)，經由工作製程及機器相關資料，先從T0搜尋機器M5的可加工作業時間區段，檢測到機器M5的時段T0至T1是閒置的，但不足以將作業O7,1分割並排入，故繼續搜尋機器M5的下一個閒置時間區段，並檢測到機器M5的時段T6至T10是閒置的，於是將第一個做作業O7,1分割並排入，接著從T10搜尋機器M4的可加工作業時間區段，因時段T14至T16與時段T23至T25都不足以將作業O7,2排入，故繼續搜尋，直至檢測到時段T30至T34與時段T40至T44足以排入第二個作業O7,2時，才將作業分割並排入，如此反覆執行，直至最後找到Job7最早可完成的時間T56後，才進行第二階段。同理，在初始排程既計畫產生後，經由MIPT法則調整後，Job4的處理時間可減少16分鐘，Job5的處理時間可減少31分鐘，Job6的處理時間可減少1分鐘，Job7的處理時間可減少17分鐘(圖七)，而平均每個Job約可減少13.8分鐘的處理時間。

　　經由本研究探討以工作為導向的啟發式排程系統之理論與方法，針對其系統特色，在解決具有不同需求的工作之排程問題時，應採取何種適當的排程方法與策略，本研究可得以下的結論。基本上，以工作為導向的啟發式排程程序每次只考量一個工作的所有作業排程規劃，必定排完一個工作的所有作業時間表後才會去排下一個工作。所以，在規劃每個工作之作業排程過程中，並不影響前面已排好的工作之作業時間表，故當製造現場的工作狀態改變時，JOH排程系統可隨機並快速地局部更動排程狀況，而不須更動整個排程計畫。

　　此外，本文所發展之JOH排程演算法，可採用前推排程法或後推排程法，滿足不同工作需求，產生不錯的初始排程結果。其特色如下所述：(1) 以前推排程法所發展之演算法，其特色是能提高資源使用率，並產生較緊密的排程結果，其藉由作業分割程序的使用，可確保工作能儘早完成 ; 再經由MIPT排程法則的調整，可使整個工作的處理時間最小化，以降低在製品的庫存。適用於緊急工作、組裝工作、交期較近或具有較低單位庫存成本的工作。(2) 以後推排程法所發展之演算法，其特色是能準時或近交期時才完成工作，以降低庫存持有成本，會產生較鬆散的排程結果。其藉由作業分割程序的使用，可提高資源使用率，並避免作業排程規劃的時間為過去的時間，可找出工作最遲需開始作業時間;再經由MIPT排程法的調整，可使整個工作的處理時間最小化，以降低在製品的庫存。適用於會延遲的工作、組裝工作及交貨期較久或具有較高單位庫存成本的工作，以避免不需要過早地開始或完成工作。