工程研究

預鑄工廠生產排程最適化模式之探討

一、前  言

    由於台灣地區建設快速發展，使得建築工程不斷地推出，在如此競爭的環境中，若能快速、經濟且能維持品質地完成，則必能搶得先機。在建築的生命週期中影響最深的是主體工程，而主體工程的完成需要大量的勞工，但因為近年來人工的成本越來越高，再加上傳統工法的性質及材料的特性，使其所要投入的時間及成本也是最多的。而在講求時效及環保意識高漲的情況下，傳統的工法漸漸地無法應付目前的需要。因此，強調時效性的預鑄工法逐漸地被引入國內，再加上政府推動營建自動化，及各種利多因素，使得預鑄廠相繼地設立。

國內建築工程在主體工程作業中，長久以來大多沿用傳統模板施工。近年來由於政府大力推動國家建設，國內營建工程界積極考慮採行預鑄工法施工，一來藉以克服技術勞力普遍短缺的問題；另方面在策略上改善施工作業流程而消除等待，並將工作簡化，藉以提昇工程品質及生產力、降低作業成本。然而由於預鑄工廠在初期設置時投資額較高，其生產計畫、鋼模數量及資源調配對於成本有關鍵性之影響。因此，如何研擬一個完整預鑄構件生產計畫、減少鋼模購置量及人工成本，將是預鑄工廠生產策略模型中重要之研究課題。

二、預鑄工廠現況

(一)預鑄工廠的生產流程

所謂「預鑄工法」即將結構物的組成單元分別地預先製作，再經由不同或類似結構單元的組合，或配合場鑄混凝土組合成結構體，有時為了實際的需要，預鑄構件亦可施加預力以增加結構的強度。而預鑄工廠就是生產預鑄單元的工廠，無論是場鑄或廠鑄，都是將原來在現場製作的單元交給預鑄廠生產，再將生產完成的版片單元運送到現場進行組裝。因此，預鑄版片的生產無論是場鑄或廠鑄，其生產流程和現場製作的流程大致上是相同的，所不同的是在預鑄廠會考慮到自動化生產及生產力的提升問題，所以將原來的生產流程，分成幾個並行的作業，同時進行，進而達到自動化及生產力的要求。

    在本模式中，主要是在資源限制下進行排程，因此，採用類似CYCLONE的方式來表現各工作站資源的流向，如圖一 ~ 圖七 。而本模式中又將生產流程依工作的相關性分成三個主要的階段，第一階段為鋼筋籠製作區，亦即工作站一；第二階段為主流程區，其中包含工作站二至工作站六；第三階段為版片修飾區，亦即工作站七，如圖八。為方便說明起見，在往後的文章中將第一階段稱為A區；第二階段稱為B區，第三階段稱為C區。在這三區中相同的資源可相互使用，以達到充分利用的目的，並在A區與B區之間，設置緩衝區(鋼筋籠堆置區)，以降低瓶頸作業對整個生產作業的影響。

(二)流程型工廠

 在B區的生產流程從組模、瓷磚鋪設到蒸汽養生，其生產步驟中有一定的程序，且每一個版片都必須經過多個不同的工作站，此種生產方式與流程型工廠(Flow Shop)的定義相同。因此，本研究採用工業工程中解決流程型工廠問題的方法，作為本模式的主要架構。

1. 流程型工廠定義

流程型工廠之定義，為一個工作(job)必須經過多個不同的機器才能完成生產的動作，而各工作在經過各機具的生產步驟中有一定的程序。

2. 求解方法

Johnson於1954年發表的Johnson rule後，針對流程型工廠排程之研究陸續有學者發表文章。Johnson rule只適用於兩部機具，對於三部以上機具的問題並不適用。在Coffman(1971)和Rinnooy Kan (1976)發表的文章中證明三部以上機具屬NP-Complete的問題，而流程型工廠屬NP-Complete的問題。Ignall and Schrage(1965)提出整數規劃(integer programming)及分枝界限法(branch-and-bound)可求得流程型工廠的最佳解(Optimal Solution)。然而，利用數學規劃或嚴謹的分析流程來搜尋最佳解，勢必花費相當多的時間，在實務應用上較不易落實，且常侷限於規模較小的排程問題。

Palmer(1965)的啟發式解法是給每個工作一個斜率指標(Slope Index)，而這個指標是基於一個工作，在依序經過的機器(machine)中，若處理的時間隨著機器的增加而有增加的傾向，則給予這個工作較高的優先排序指標；反之，若有減少的傾向，則給予這個工作較低的優先排序指標。Gupta(1971)也是計算每個工作的排序指標，用來決定生產的順序。Campbell , Dudek and Smith (CDS) (1970)的啟發式解法則是將Johnson法則延伸，將Ｍ個machine的問題，分成M-1個兩個machine的問題，再以Johnson法則對Ｍ-1個問題進行排序，進而找到較佳的排序。Dannenbring(1977) 則是將Palmer和CDS結合，發展出RA(rapid access)的啟發式解法，將Ｎ個job的Ｍ個machine的問題，轉成一個Ｎ個job兩個machine的問題，再以Johnson法則決定順序。Nawaz, Enscore and Ham(NEH)(1983)則根據一個工作在經過每個machine的總流程時間，較長者有優先進行排序的觀念。首先選擇兩個總流程時間最長的工作進行排序，找到流程時間最少的排列順序，再以此排列順序將總流程時間第三長的工作以插入的方式進行排序，得到三個工作下的最佳排列方式，其他的工作就是以此種插入的方式得到最佳排列組合。Hundal and Rajgopal(1988)認為Palmer的方法在Job越大時所得到的結果誤差越大，因此，他對Palmer的指標做了一些改善，使每個工作都有兩個指標，而每個工作以這兩個指標個別排序，產生兩種排列方式，較好的則為最後的排列順序。Taillard(1990)則是運用Tabu的方式找到排序的組合；Ogbu and Smith(1990)以模擬退火的方式找出排列順序；Ho and Chang(1991)則是以求得在排序中最小的gap，進而得到啟發式解。而近幾年來，陸續發展出各種新式的演算法，如Cleveland and Smith (1989)，Reeve (1993)，Chen,Vempati and Aljaber (1995)，[Chan 1999]利用基因遺傳演算法(Genetic Algorithms)作為求解的工具。[Chan 1999]並運用在預鑄廠的生產上，但只針對預鑄廠B區的部份，且未考慮到資源限制的情況。

由上述之討論看來，在求解的方法上，多偏向使用啟發式解，且在資源限制上的討論幾乎是微乎其微，其緣故主要是由於解析法一方面所要耗用的計算機資源太過龐大；另一方面是因為模式的建立並不容易、適用範圍不大、彈性較小。

然而，啟發式的方法固然有其簡便的優點，但由於其乃是訂立一些規則來求取良好的解，而這些原則並不一定適用所有情況，因此在實用上受到限制。再就一般工程人員而言，並無法容易地使用以上方法來規劃排程。

(三)生產流程的影響因子

由以上的生產流程、資源流向及預鑄廠的特性，可歸納出影響生產流程的因子有以下幾點 : (1)人工(2)天車(3)鋼筋籠堆置區及蒸汽養生的啟動數量的大小(4)多專案需求(5)共同資源的分享與否，其相互關係如圖九 。由圖中可看出，共同資源的分享與否及到期日的改變，會影響人工、天車、鋼筋籠堆置區大小及蒸汽養生數量對總流程時間的影響。

(四)資源的取用順序

 本研究主要是在探討多專案且資源限制下的情況。因此，本研究中採用派工法則的觀念，決定各工作取用資源的順序。在本模式中，以現場工作人員最易判斷的先到者先服務(FCFS)的方式，作為取用資源的依據; 先到者，優先取得資源。

(五)多專案的考量

 預鑄廠的生產通常必須配合工地做不同的生產計畫，而不同的工地有不同的到期日要求。在本研究中，在考量到期日對總流程時間的影響時，為使專案一與專案二都能達到到期日的要求，在本模式採用如圖十 中，due day difference (project2 due day- project1 due day)的觀念，也就是在Makespan(FT_max)求出後，在due day difference之間，不能有專案一版片的生產。

三、研究方法

基因遺傳法已被廣泛應用於各類的最佳化問題，而本研究亦將以基因遺傳法建構排程模式，茲將基因遺傳法介紹如下:

(一)基因遺傳法介紹

基因遺傳法（Genetic Algorithm）是在1970年代由University of Michigan 的John Holland教授提出，而後廣泛應用於商業、科學以及工程等各種領域中。

基因遺傳法是一種仿效自然選擇及基因遺傳機制的搜尋技術，其原理是根據達爾文的進化論模擬自然界適者生存的原則，藉由隨機性的選取、基因配對交換（crossover）以及基因突變（mutation）產生後代（offspring）。再由目標值所構成的外界環境評估個體之適應程度（fitness），根據其適應程度的高低進行複製（reproduction），而產生新的族群。這些新產生出來的族群就作為搜尋的新出發點，對整個搜尋空間做逐次的搜尋，經過數代之後找到一或多個適合此一環境之解，以下針對本研究的運作流程逐一說明。

(二)編碼與解碼

   在本模式中，因為每個工作所要經過的工作站有相同的程序，因此，只要決定每個工作的生產順序即可。在本模式中，吾人以Bean(1994)所提出Random numbers代表各工作生產順序的指標。

          字串：【0.9,0.62,0.5,0.85,0.13,0.29,0.16,0.4,0.8】

       •解碼：

 (三)運算元決定

基因遺傳法的運算元包含了交換運算元與突變運算元，在本模式中交換運算元是利用UX3選取子字串的觀念，發展出RUX3；而突變運算元是利用UM3的觀念發展出RUM3。

1. RUX3：

UX3原本是適用於有固定先行後續的排序問題的交換運算元，但在本模式中的排序問題上每個字元的random number就好比先行後續的關係，因此，本模式結合UX3及random number，發展出RUX3，步驟如下:

(1)選取親代字串父代字串1 及父代字串2之兩個交換位置，設為2，6，如圖十一 所示。

(2)找出父代字串1被選取之次字串（即3456），以及在父代字串2中按照父代字串2之字元次序且不與父代字串１重複之字元，如圖十二 所示。

(3)比較random number的大小，選取字元填入新的子字串之中，如圖十三 所示。

(4)父代字串2可依同樣步驟，找到新的子字串，如圖十四 所示。

2. RUM3：

    UM3的原理與UX3大致相同，只是其不做交換，而是選取某一字串中的子字串，將子字串按UX3之原理重新排列。在本模式中則是結合UM3與random number，發展出RUM3。其過程為選取某一字串中的子字串，隨機給予random number，再將字串重新排列，步驟如下。

(1)選取親代字串父代字串1之兩個交換位置，設為2，6，如圖十五 所示。

(2)找出父代字串1被選取之次字串（即3456），隨機給予random number，如圖十六 所示。

(3)比較random number的大小，選取字元填入新的子字串之中，如圖十七 所示。

(四)目標值評估
    本研究以最低成本做為目標值來評估字串的優劣，字串之適合度則計算如下：

其中， 表示目標值， 表示適合度函數，而 則是目前世代中的第 個字串； 為一0到1之間的常數，其功用為：(1)避免分母為零的狀況；(2)避免適合度皆為線性關係，使再生的選取時能更接近隨機選取，在本模式中將 定為0.5。

(五)選取(Selection)

在選取（Selection）運算中，除了使用Roulette Wheel Method外，為了使搜尋的過程更有效率，茲再加入了一菁英（Elitist）策略。此一策略之的目的乃將上一代的最佳結果無條件保留至下一代。但為不造成過早的收斂，每代僅保留一個上一代表現最佳的字串為限。

(六)基因遺傳法的特色

整體來看，基因遺傳法的搜尋方式有點類似隨機搜尋，但卻不完全是隨機搜尋，因為基因遺傳法有其自成系統的基因運算元，以及適者生存的再生法則，茲列出其不同於一般演算法的特色如下：

1.直接使用以字元組成的字串（string）搜尋，亦即是以可行解的編碼字串來進行搜尋，而非可行解本身。

2.以一個族群（多點）來進行搜尋，而非以單獨一點。

3.直接由目標函數的資訊進行搜尋，而不用輔知識。

4.以適合度的觀念來決定搜尋點的優劣。

5.進行搜尋的過程並非經由固定的路徑，而是經由計算出的機率配合隨機性的產生。

6.使用一些隨機的操作，這些操作包含選取（Selection）、交換（Crossover）以及突變（Mutation），然而這些操作並非僅是盲目的動作，而是在隨機進行的過程中包含了他們所要傳達的資訊。

四、模式建立

基於第二章討論，本研究將生產流程分成A