碩士班一年級

詹禮豪
彭彥凱
梁瀠方
朱庭萱

碩士班二年級

李育真
卓志諺
黃霈宜
史瑞涵
黃靖涵

歷屆學長姊

2013
本研究利用電腦模擬實驗比較各種應用在旅館業營收管理的動態決策方法。此隨機問題環境為在旅館的房間數有限,且訂房需求之顧客來到為非同質性的卜瓦松過程(non-homogeneous Poisson process)的情況下,旅館業者應如何決策是否接受該顧客之訂位要求以最大化營收。在本問題中,顧客隨機地來到,且依不同的入住時間、住房天數、房型偏好、及願意支付的價錢而分成不同顧客類別。在實際問題中,當有顧客欲訂房時,旅館業者必須立刻決定是否要接受該顧客的訂房需求。若是允諾該顧客之訂房需求,則對於旅館來說,在該顧客之住房期間將會減少一間可使用的房間,並增加此顧客所帶來的收益。若是拒絕該顧客之訂房,則有機會將該房間出租給未來可以帶來更高營收的顧客。Hung and Lai (2010)提出一動態決策方法-模擬期望收益決策步驟法(simulated expected revenue decision procedure, SER),用以幫助業者做出決策。從其實驗結果發現SER表現出色。因此,本研究透過電腦模擬實驗比較SER與其他決策方法的績效。

本研究依據房間等級數及價格等級數的不同,分成三種不同複雜程度的問題。首先是單一房間等級及單一價格等級的問題,再來是單一房間等級、多種價格等級的問題,最後將問題延伸到多種房間等級且每種房間等級均有多種價格等級。而在多房間等級且允許顧客可升級房間等級的假設下,本研究考慮顧客在住房期間可以變換房間類型及不可變換房間類型兩種情況。在三種不同複雜度的問題下,本研究發現模擬期望收益決策步驟法所獲得的營收與完美資訊下所獲得的最佳營收差距為最小;在改變問題控制因子下,模擬期望收益決策步驟法的表現變異不大。總體而言,模擬期望收益決策步驟法在不同的問題假設下均有穩定且良好的表現。
生產排程(Production scheduling)是在各種有限的生產資源下來安排不同工件(job)的投入時間。本研究將機台視為生產資源,探討單一機台(Single-machine)的生產排程問題。各工件相關的屬性(Attributes)有可加工時間(Ready date)、工件交期(Due date)、加工時間(Processing time)及工件權重(Weight)。本研究假設每個工件有不同的可加工時間與交期,且工件只能在可加工時間到工件交期的時段內加工,不允許延期加工。因此,對於每一工件而言,我們僅能挑選來加工或是拒絕。此外,在工件加工期間,不允許中斷或被其他工件強占(Non-preemption)。本研究著重的生產排程問題為最大化權重排程問題(Weight maximization problem),以往文獻將此問題稱為最大化產出量問題(Throughput maximization problem)。

本研究提出三個方法來求解最大化權重排程問題,分別是(1)啟發式演算法(Heuristic method);(2)混合整數規劃(Mixed integer programming)及(3)分枝界限法(Brand-and-bound method)。其中,啟發式演算法可求得一初解供混合整數規劃及分枝界限法利用。本研究發展出兩個部份排序(Partial ordering)、四個支配法則(Dominance rule)以及利用線性規劃放鬆(Linear programming relaxation)模型求出界限,以降低分枝界限法的運算時間。

在本研究的研究結果中,於分枝界限法中使用部份排序,可在極短時間內求得一個鄰近最佳解,因此若在有限的時間內,我們可以利用部份排序來求解,而不需求得最佳解。此外,支配法則與線性規劃放鬆模型可降低分枝界限法中搜尋樹的節點數,有效縮減求解的運算時間。
對於成衣產業的生產製程而言,首要的目標為最大化產出,而產出的多寡是由車縫製程─即成衣生產流程中的瓶頸製程之排程規劃所決定;次要的目標則是最小化裁切製程時所產生的布料浪費,裁切計畫影響此項目標。裁片為車縫製程(瓶頸)上游之裁切製程所產出的半成品。由於過多的裁片不僅會增加儲存的成本,也會造成現場管理的困難,因此第三個目標為最小化裁片的庫存水準,且裁片的庫存水準是取決於裁切製程的排程規劃。根據目標的優序,車縫排程以及裁切計畫必須要優先被決定,至於裁切製程的排程則必須遵照已訂定之車縫排程及裁切計畫進行後續規劃。當裁切部門在決定各裁切工作適當的裁切時間時,除了需確保所有車縫生產線(瓶頸)不會因缺少裁片而閒置,也需考慮已排定裁切計畫之各裁切工作對應產出之多餘裁片種類,盡量降低裁片的在製品庫存。因此本論文將車縫排程以及裁切計畫作為已知的資訊,將滿足車縫線排程之生產需求做為限制條件,以最小化裁片之庫存水準為目標,探討如何進行裁切排程。

論文中針對成衣工廠中的裁切排程問題提出了混合整數規劃及啟發式方法。實驗結果顯示,裁切床數多寡對於混合整數規劃的求解速度有決定性的影響,而啟發式方法在大部分的問題中雖無法提供與混合整數規劃一樣良好的解,但都能在極短時間內求解完成。因此我們建議結合兩種方法,將啟發式方法的解做為混合整數規劃的起始解。實驗結果顯示在大型問題中顯著地改善了求解的效率。
對於成衣產業的生產製程而言,首要的目標為最大化產出,而產出的多寡是由車縫製程─即成衣生產流程中的瓶頸製程之排程規劃所決定;次要的目標則是最小化裁切製程時所產生的布料浪費,裁切計畫影響此項目標。裁片為車縫製程(瓶頸)上游之裁切製程所產出的半成品。由於過多的裁片不僅會增加儲存的成本,也會造成現場管理的困難,因此第三個目標為最小化裁片的庫存水準,且裁片的庫存水準是取決於裁切製程的排程規劃。根據目標的優序,車縫排程以及裁切計畫必須要優先被決定,至於裁切製程的排程則必須遵照已訂定之車縫排程及裁切計畫進行後續規劃。當裁切部門在決定各裁切工作適當的裁切時間時,除了需確保所有車縫生產線(瓶頸)不會因缺少裁片而閒置,也需考慮已排定裁切計畫之各裁切工作對應產出之多餘裁片種類,盡量降低裁片的在製品庫存。因此本論文將車縫排程以及裁切計畫作為已知的資訊,將滿足車縫線排程之生產需求做為限制條件,以最小化裁片之庫存水準為目標,探討如何進行裁切排程。

論文中針對成衣工廠中的裁切排程問題提出了混合整數規劃及啟發式方法。實驗結果顯示,裁切床數多寡對於混合整數規劃的求解速度有決定性的影響,而啟發式方法在大部分的問題中雖無法提供與混合整數規劃一樣良好的解,但都能在極短時間內求解完成。因此我們建議結合兩種方法,將啟發式方法的解做為混合整數規劃的起始解。實驗結果顯示在大型問題中顯著地改善了求解的效率。
本論文研究隨機存貨配給問題。倉庫管理者會依據訂單缺貨成本的大小,將訂單分成數種不同的等級。當倉庫管理者拒絕訂單的等級越高,所產生的缺貨成本越大。所探討的隨機存貨配給問題假設為訂單來到服從卜瓦松過程和訂單需求量為隨機變數,決策的目標為如何有效分配有限的倉庫存貨量以達到最小化總缺貨成本。本研究利用抽樣期望成本差決策步驟(Sampling expected cost gap decision procedure, SECG)決定是否滿足目前的訂單或是應該保留存貨給未來較大缺貨成本的訂單。抽樣期望成本差決策步驟的過程中,在各個抽樣的情境下我們需要求解存貨分配問題。因此,在已知各等級訂單的來到個數與訂單的需求量,我們分別使用兩種存貨分配方法,一種是利用0/1背包問題的數學模型求得最佳分配決策。使用最佳分配方法所耗費的計算時間較長,因此,為使計算時間縮短,我們提出另一種分配決策方法-啟發式演算法。

根據模擬實驗結果得知,SECG分別採用兩種存貨分配方法的總缺貨成本和在完美資訊下之最佳決策極為接近,並且兩個分配法之SECG與完美資訊最佳決策的差距皆小於1%,兩者表現非常接近。但採用0/1背包問題的數學模型的績效會略優於採用啟發式演算法。然而,採用前者的計算時間會長於採用後者。除此之外,在不同問題因子水準下,兩種配給方法皆有非常穩定的表現。
2012
生產排程(Production scheduling)是在各種有限的生產資源下來安排不同工件(job)的投入時間。本研究將機台視為生產資源,探討單一機台(Single-machine)的生產排程問題。各工件相關的屬性(Attributes)有可加工時間(Ready date)、工件交期(Due date)、加工時間(Processing time)及工件權重(Weight)。本研究假設每個工件有不同的可加工時間與交期,且工件只能在可加工時間到工件交期的時段內加工,不允許延期加工。因此,對於每一工件而言,我們僅能挑選來加工或是拒絕。此外,在工件加工期間,不允許中斷或被其他工件強占(Non-preemption)。本研究著重的生產排程問題為最大化權重排程問題(Weight maximization problem),以往文獻將此問題稱為最大化產出量問題(Throughput maximization problem)。

本研究提出三個方法來求解最大化權重排程問題,分別是(1)啟發式演算法(Heuristic method);(2)混合整數規劃(Mixed integer programming)及(3)分枝界限法(Brand-and-bound method)。其中,啟發式演算法可求得一初解供混合整數規劃及分枝界限法利用。本研究發展出兩個部份排序(Partial ordering)、四個支配法則(Dominance rule)以及利用線性規劃放鬆(Linear programming relaxation)模型求出界限,以降低分枝界限法的運算時間。

在本研究的研究結果中,於分枝界限法中使用部份排序,可在極短時間內求得一個鄰近最佳解,因此若在有限的時間內,我們可以利用部份排序來求解,而不需求得最佳解。此外,支配法則與線性規劃放鬆模型可降低分枝界限法中搜尋樹的節點數,有效縮減求解的運算時間。
對於成衣產業的生產製程而言,首要的目標為最大化產出,而產出的多寡是由車縫製程─即成衣生產流程中的瓶頸製程之排程規劃所決定;次要的目標則是最小化裁切製程時所產生的布料浪費,裁切計畫影響此項目標。裁片為車縫製程(瓶頸)上游之裁切製程所產出的半成品。由於過多的裁片不僅會增加儲存的成本,也會造成現場管理的困難,因此第三個目標為最小化裁片的庫存水準,且裁片的庫存水準是取決於裁切製程的排程規劃。根據目標的優序,車縫排程以及裁切計畫必須要優先被決定,至於裁切製程的排程則必須遵照已訂定之車縫排程及裁切計畫進行後續規劃。當裁切部門在決定各裁切工作適當的裁切時間時,除了需確保所有車縫生產線(瓶頸)不會因缺少裁片而閒置,也需考慮已排定裁切計畫之各裁切工作對應產出之多餘裁片種類,盡量降低裁片的在製品庫存。因此本論文將車縫排程以及裁切計畫作為已知的資訊,將滿足車縫線排程之生產需求做為限制條件,以最小化裁片之庫存水準為目標,探討如何進行裁切排程。

論文中針對成衣工廠中的裁切排程問題提出了混合整數規劃及啟發式方法。實驗結果顯示,裁切床數多寡對於混合整數規劃的求解速度有決定性的影響,而啟發式方法在大部分的問題中雖無法提供與混合整數規劃一樣良好的解,但都能在極短時間內求解完成。因此我們建議結合兩種方法,將啟發式方法的解做為混合整數規劃的起始解。實驗結果顯示在大型問題中顯著地改善了求解的效率。
本論文研究隨機存貨配給問題。倉庫管理者會依據訂單缺貨成本的大小,將訂單分成數種不同的等級。當倉庫管理者拒絕訂單的等級越高,所產生的缺貨成本越大。所探討的隨機存貨配給問題假設為訂單來到服從卜瓦松過程和訂單需求量為隨機變數,決策的目標為如何有效分配有限的倉庫存貨量以達到最小化總缺貨成本。本研究利用抽樣期望成本差決策步驟(Sampling expected cost gap decision procedure, SECG)決定是否滿足目前的訂單或是應該保留存貨給未來較大缺貨成本的訂單。抽樣期望成本差決策步驟的過程中,在各個抽樣的情境下我們需要求解存貨分配問題。因此,在已知各等級訂單的來到個數與訂單的需求量,我們分別使用兩種存貨分配方法,一種是利用0/1背包問題的數學模型求得最佳分配決策。使用最佳分配方法所耗費的計算時間較長,因此,為使計算時間縮短,我們提出另一種分配決策方法-啟發式演算法。

根據模擬實驗結果得知,SECG分別採用兩種存貨分配方法的總缺貨成本和在完美資訊下之最佳決策極為接近,並且兩個分配法之SECG與完美資訊最佳決策的差距皆小於1%,兩者表現非常接近。但採用0/1背包問題的數學模型的績效會略優於採用啟發式演算法。然而,採用前者的計算時間會長於採用後者。除此之外,在不同問題因子水準下,兩種配給方法皆有非常穩定的表現。
2011
本研究利用電腦模擬實驗比較各種應用在旅館業營收管理的動態決策方法。此隨機問題環境為在旅館的房間數有限,且訂房需求之顧客來到為非同質性的卜瓦松過程(non-homogeneous Poisson process)的情況下,旅館業者應如何決策是否接受該顧客之訂位要求以最大化營收。在本問題中,顧客隨機地來到,且依不同的入住時間、住房天數、房型偏好、及願意支付的價錢而分成不同顧客類別。在實際問題中,當有顧客欲訂房時,旅館業者必須立刻決定是否要接受該顧客的訂房需求。若是允諾該顧客之訂房需求,則對於旅館來說,在該顧客之住房期間將會減少一間可使用的房間,並增加此顧客所帶來的收益。若是拒絕該顧客之訂房,則有機會將該房間出租給未來可以帶來更高營收的顧客。Hung and Lai (2010)提出一動態決策方法-模擬期望收益決策步驟法(simulated expected revenue decision procedure, SER),用以幫助業者做出決策。從其實驗結果發現SER表現出色。因此,本研究透過電腦模擬實驗比較SER與其他決策方法的績效。

本研究依據房間等級數及價格等級數的不同,分成三種不同複雜程度的問題。首先是單一房間等級及單一價格等級的問題,再來是單一房間等級、多種價格等級的問題,最後將問題延伸到多種房間等級且每種房間等級均有多種價格等級。而在多房間等級且允許顧客可升級房間等級的假設下,本研究考慮顧客在住房期間可以變換房間類型及不可變換房間類型兩種情況。在三種不同複雜度的問題下,本研究發現模擬期望收益決策步驟法所獲得的營收與完美資訊下所獲得的最佳營收差距為最小;在改變問題控制因子下,模擬期望收益決策步驟法的表現變異不大。總體而言,模擬期望收益決策步驟法在不同的問題假設下均有穩定且良好的表現。
生產排程(Production scheduling)是在各種有限的生產資源下來安排不同工件(job)的投入時間。本研究將機台視為生產資源,探討單一機台(Single-machine)的生產排程問題。各工件相關的屬性(Attributes)有可加工時間(Ready date)、工件交期(Due date)、加工時間(Processing time)及工件權重(Weight)。本研究假設每個工件有不同的可加工時間與交期,且工件只能在可加工時間到工件交期的時段內加工,不允許延期加工。因此,對於每一工件而言,我們僅能挑選來加工或是拒絕。此外,在工件加工期間,不允許中斷或被其他工件強占(Non-preemption)。本研究著重的生產排程問題為最大化權重排程問題(Weight maximization problem),以往文獻將此問題稱為最大化產出量問題(Throughput maximization problem)。

本研究提出三個方法來求解最大化權重排程問題,分別是(1)啟發式演算法(Heuristic method);(2)混合整數規劃(Mixed integer programming)及(3)分枝界限法(Brand-and-bound method)。其中,啟發式演算法可求得一初解供混合整數規劃及分枝界限法利用。本研究發展出兩個部份排序(Partial ordering)、四個支配法則(Dominance rule)以及利用線性規劃放鬆(Linear programming relaxation)模型求出界限,以降低分枝界限法的運算時間。

在本研究的研究結果中,於分枝界限法中使用部份排序,可在極短時間內求得一個鄰近最佳解,因此若在有限的時間內,我們可以利用部份排序來求解,而不需求得最佳解。此外,支配法則與線性規劃放鬆模型可降低分枝界限法中搜尋樹的節點數,有效縮減求解的運算時間。
對於成衣產業的生產製程而言,首要的目標為最大化產出,而產出的多寡是由車縫製程─即成衣生產流程中的瓶頸製程之排程規劃所決定;次要的目標則是最小化裁切製程時所產生的布料浪費,裁切計畫影響此項目標。裁片為車縫製程(瓶頸)上游之裁切製程所產出的半成品。由於過多的裁片不僅會增加儲存的成本,也會造成現場管理的困難,因此第三個目標為最小化裁片的庫存水準,且裁片的庫存水準是取決於裁切製程的排程規劃。根據目標的優序,車縫排程以及裁切計畫必須要優先被決定,至於裁切製程的排程則必須遵照已訂定之車縫排程及裁切計畫進行後續規劃。當裁切部門在決定各裁切工作適當的裁切時間時,除了需確保所有車縫生產線(瓶頸)不會因缺少裁片而閒置,也需考慮已排定裁切計畫之各裁切工作對應產出之多餘裁片種類,盡量降低裁片的在製品庫存。因此本論文將車縫排程以及裁切計畫作為已知的資訊,將滿足車縫線排程之生產需求做為限制條件,以最小化裁片之庫存水準為目標,探討如何進行裁切排程。

論文中針對成衣工廠中的裁切排程問題提出了混合整數規劃及啟發式方法。實驗結果顯示,裁切床數多寡對於混合整數規劃的求解速度有決定性的影響,而啟發式方法在大部分的問題中雖無法提供與混合整數規劃一樣良好的解,但都能在極短時間內求解完成。因此我們建議結合兩種方法,將啟發式方法的解做為混合整數規劃的起始解。實驗結果顯示在大型問題中顯著地改善了求解的效率。
本論文研究隨機存貨配給問題。倉庫管理者會依據訂單缺貨成本的大小,將訂單分成數種不同的等級。當倉庫管理者拒絕訂單的等級越高,所產生的缺貨成本越大。所探討的隨機存貨配給問題假設為訂單來到服從卜瓦松過程和訂單需求量為隨機變數,決策的目標為如何有效分配有限的倉庫存貨量以達到最小化總缺貨成本。本研究利用抽樣期望成本差決策步驟(Sampling expected cost gap decision procedure, SECG)決定是否滿足目前的訂單或是應該保留存貨給未來較大缺貨成本的訂單。抽樣期望成本差決策步驟的過程中,在各個抽樣的情境下我們需要求解存貨分配問題。因此,在已知各等級訂單的來到個數與訂單的需求量,我們分別使用兩種存貨分配方法,一種是利用0/1背包問題的數學模型求得最佳分配決策。使用最佳分配方法所耗費的計算時間較長,因此,為使計算時間縮短,我們提出另一種分配決策方法-啟發式演算法。

根據模擬實驗結果得知,SECG分別採用兩種存貨分配方法的總缺貨成本和在完美資訊下之最佳決策極為接近,並且兩個分配法之SECG與完美資訊最佳決策的差距皆小於1%,兩者表現非常接近。但採用0/1背包問題的數學模型的績效會略優於採用啟發式演算法。然而,採用前者的計算時間會長於採用後者。除此之外,在不同問題因子水準下,兩種配給方法皆有非常穩定的表現。
2010
本研究為收益管理於飯店業的應用。本研究主要探討的隨機問題為:在飯店的房間數有限,且訂房需求之來到服從非同質性的卜瓦松過程的情況下,飯店業者應如何妥善分配房間。在飯店業,顧客在規劃期間內隨機地來到,且依不同的入住時間、住房天數、房型偏好、及願意出的價錢而可能為業者帶來不同的收益。當有顧客訂房時,飯店業者必須立刻決定是否要接受該顧客的訂房需求。本研究提出一決策步 驟-模擬期望價差決策步驟 (simulated expected revenue gap decision procedure, SERG) ,以幫助飯店業者決定是否應該接受目前來到的顧客並且立刻獲利,或是應該要保留房間給未來可能帶來更高受益的顧客。

本研究依據房間等級數量及價格等級數量的不同,考慮三種不同複雜程度的問題。在多房間等級的假設下, 本研究另外考慮顧客在住房期間可以變換房型及不可變換房型兩種情況,因此提出兩種模擬期望價差決策步驟。 根據模擬實驗的結果得知,在單一房間等級及單一價格等級的假設下, 模擬期望價差決策步驟所獲得之收益與完美資訊下所獲得之收益極為相近,其差距僅有 0.21% 。 在單一房間等級及多價格等級的假設下,差距為 0.94% 。 而在多房間等級 及多價格等級 的假設下,可以變換房型及不可變換房型兩種情況所獲得的收益與完美資訊 下所獲得之收益 的差距分 別為 1.35% 及 1.81% 。當問題較為複 雜時,模擬期望價差決策步驟之收益與完美資訊下之收益的差距略為提高。總體而言, 在不同的問題假設下, 模擬期望價差決策步驟 有非常穩定且傑出的表現;同時, 模擬期望價差決策步驟 能夠在短時間內答覆顧客的訂位需求。
本論文提出混合整數規劃求解高科技產業產能擴充專案問題。對高科技產業而言,產能擴充專案通常分成數個階段執行,前一階段完成後,才可繼續展開下一階段,而每一階段則包含數個具有順序關係的作業。在考慮未來需求與作業成本不確定性的情形下,本論文將此一產能擴充問題建構成隨機專案排程問題,並考量各作業前置時間、預算限制、資金調度因素於混合整數規劃模型中。目的為最佳化各作業的執行時間點與產能擴充量,以最小化期望缺貨成本、產能過剩成本與作業執行成本。最後,本論文針對需求機率、缺貨成本與產能過剩成本比率、資金的充足性進行實驗,藉此觀察與驗證模型的績效。
對於在成衣工廠的裁切製程而言,其首要目標為滿足下游的車縫製程;因車縫製程是成衣工廠的瓶頸製程,故裁切部門必須確保裁切製程所裁出的半成品能及時送到車縫製程進行加工。在裁切部門中,一個裁切床可以裁出許多不同尺寸、不同顏色的衣服零件,也就是半成品;而為了避免車縫製程因缺少半成品而出現閒置的情況,所以裁切部門必須對各裁切床決定適當的裁切時間,以確保車縫製程的需求皆能被滿足。而由於裁切出的半成品為片狀的衣服零件,管理半成品庫存不易,故裁切部門也希望能降低其半成品的庫存量。因此,此篇論文將考慮如何為各裁切床決定出理想的裁切完工時間以滿足車縫製程的需求,同時還能降低裁切部門的半成品庫存量。

本篇論文中針對在成衣工廠中出現的裁切製程排程問題,提出一個混整數的求解模型以及一個啟發式的求解方法來幫助解決問題。本篇論文將滿足車縫線需求視為限制式,並將最小化半成品庫存量當作目標式。由實驗結果顯示,混整數模型與啟發式求解法在小型問題時皆有很好的求解績效;而在中、大型問題時,雖然啟發式求解法的求解不如混整數模型來得好,但考慮到混整數模型在解中、大型問題時需要很長的求解時間,故求解中、大型問題時,仍推薦使用啟發式求解法。
本研究主要探討在需求不確定性以及採購價格不確定性下,利用多種類型採購方式的多期採購計劃。我們將問題建構成一個混合整數規劃並考量多種情境模式,其目標為最小化期望總成本。多種類型採購方式包含 : 長期合約、 Option 合約、 Flexible 合約以及現貨市場。一般而言,長期合約提供最低的採購價格,但其採購限制較為缺乏彈性且採購數量較多。而 Option 合約與 Flexible 合約的價格相對於長期合約是比較高,但其採購限制較長期合約有彈性。現貨市場價格主要隨著市場需求而改變。通常現貨市場價格會高於合約的採購價格,但在少數的情況下現貨市場價格會是最便宜的採購選擇。在本研究的實驗中,我們求解不同條件下的採購計劃,並探討各種類型的採購數量之變化。研究數據顯示,本研究所提出的混合整數模型可有效的利用不同類型的採購方式來最小化總採購成本。
2009
本論文主要在探討當工作可分割時之等效平行機台排程問題。在本問題中,假設一個工作可以被分成許多的子工作,並且可將這些子工作指派到不同的機台上同時加工。每個工作具有已知的加工時間、準備時間以及交期。在機台加工過程中,當欲加工工作與前一加工工作不同時,必須耗費一相依整備時間方能進行加工。為最小化此問題之總延遲時間,本論文提出一個兩階段式方法來求解此問題。第一階段中,本論文提出五種初步排程產生方法。接著在第二階段中,將在第一階段產生的排程中有延遲的工作或子工作做進一步分割,並將分割後的子工作重新指派到機台上以減少總延遲時間。由實驗結果顯示,本論提出之方法表現優於前人所提出之方法。
近十年來服務業成長很快,競爭激烈。對服務業來說,如何有效利用人力資源是一個重要的課題。客服中心的營運尤其是現今企業的重要服務之ㄧ。本篇論文利用搜尋法和影價鄰近解評估求解客服中心之人員排班問題。為了使不同的技能需求達到最大的滿足,目標值是要找出一最佳排班表使所缺乏的人力資源成本為最少。

在本篇論文研究中,給定各時間區段有變動需求、和配合政府法規、公會限制、公司內部規定的已知客服人員班別類型並由四種搜尋法 :傳統的 模擬退火法和塔布搜尋法、和利用影價鄰近解評估 的 模擬退火法和塔布搜尋法來求解客服中心人員排班問題。最後實驗顯示四種搜尋法中,利用影價鄰近解評估的塔布搜尋法表現最好。
航空業者可以將飛機上同一艙等的相同座位以不同的價格販賣給顧客。由於每位顧客對於價格的接受程度不同,航空業者會根據需求預測,將顧客區分為數種費率等級;顧客的費率等級越高,表示該等級顧客的消費金額較其他等級顧客為高。每當有顧客來到,決策者必須立即決定是否要滿足該顧客的訂位。為了增加收益,決策者會希望拒絕部分低等級顧客的需求並且保留座位給等級較高的顧客。本論文考慮一個將顧客區分為多種等級的單一航班問題,顧客來到服從非同質性的卜瓦松過程。決策者的目標是使每ㄧ航班的收益最大。

本論文提出了兩種方法針對每一位來到的顧客進行滿足與否其需求之判斷,此兩種方法分別是動態座位配給決策步驟 (dynamic seat rationing decision procedure) 以及期望收益價差決策步驟 (expected revenue gap decision procedure) 。根據模擬實驗的結果可知,期望收益價差決策步驟相較於先前的研究方法而言,能夠更有效的提升最大收益,並且在不同的實驗條件下,期望收益價差決策步驟皆有非常穩定的表現。
本研究提出演算法來求解單一專案、作業不可中斷性的無限作業執行模式之資源限制專案排程問題,專案中每一個作業之作業強度在執行期間是不可變動且資源可重覆使用,目標在於最小化專案的總完工時間。我們利用片段線性曲線去近似作業執行時間與作業強度所構成的連續型非線性曲線關係,若專案排程問題利用片段線性曲線去近似非線性曲線關係,在本研究中我們稱之為近似問題。

吳【 2007 】提出的分枝窮舉法,經由窮舉方式我們可以得到近似問題的最佳解,但隨著問題的作業數目增加,利用窮舉法將降低求解效率;對於大型的問題,分枝窮舉法不夠有效率,因此本研究利用啟發式演算法來求解問題,並且分成兩個階段來求解,第一階段包含三種啟發式求解方法,首先是王【 2008 】提出的複次 Boctor 演算法,針對大型的問題,它能夠非常有效率的求解近似問題,不過求解品質是三種啟發式求解方法中最差;本研究提出兩種集束搜尋法希望能在合理的計算時間內得到一個不錯的專案排程解,分別是以作業為分枝基礎的集束搜尋法與以事件為分枝基礎的集束搜尋法,它們都是搭配 Boctor 【 1996 】演算法與吳【 2007 】線性規劃來求解近似問題,目的是希望縮短近似問題的求解時間;第二階段利用兩種啟發式搜尋法 --- 塔布搜尋法以及模擬退火法,將第一階段得到較好的求解結果在合理的計算時間內再加以改善。

本研究根據實驗與統計分析,決定出這兩種集束搜尋法的控制參數並比較其績效表現,在第一階段,我們先比較複次 Boctor 演算法與這兩種集束搜尋法對近似問題的求解結果,挑選出這三個啟發式方法中表現較好的事件順序解,發現以事件為分枝基礎的集束搜尋法得到的平均專案完工時間最小;在第二階段,我們發現在給定相同的電腦計算時間內模擬退火法改善比塔布搜尋法好。
2008
近年來成衣業面臨全球化市場競爭愈演愈烈的趨勢,對於現今成衣生產者而言,準時交貨以及有效降低生產成本, 便成了兩項最重要的課題,因此,一套生產排程系統將是一個不可或缺的工具。絕大多數成衣製造流程之瓶頸皆為車縫製程,故本研究專注於成衣廠車縫製程的生產排程,提出一個兩階段方法來求解本問題,且兩階段各有一個不同的目標式。第一階段之目標式為最小化最大延遲時間,本研究證明出多條生產線之車縫製程排程問題能被轉換為單一機台問題,再利用一個派工法則(可插位最早交期法則)即可得到本階段之最佳排程;第二階段則是基於第一階段之結果,建構一個目標式為最小化生產成本之混合整數規劃,進而得到一最佳排程。經實驗驗證本研究方法之成效,顯示本方法可在合理之求解時間內獲得一近似最佳解。
當接單式 (make-to-order) 生產系統的製造商面對期望需求大於現有產能的情形下,應該多接受高獲利的訂單和拒絕低獲利的訂單,這樣才可妥善利用有限的產能使得獲利最大化。然而,在未來會有各式各樣的訂單在不同的時間到達,所以製造商無法同時得知所有訂單的資訊並且選擇最高利潤的訂單。故當一筆查詢訂單到達時,製造商必須在不知道未來實際訂單的資訊下做出決策,該接受此筆訂單還是拒絕,如此才可以保存產能給未來高獲利的訂單。

  本篇研究主要參考參考洪 and 李 【 2007 】所提出的 決策模型,其方法著重於解決像此類的訂單選擇決策問題,且基本的假設有: (1) 未來顧客訂單的到達是一個普瓦松過程 (Poisson process) 。 (2) 未來顧客訂單的產能需求量是一個連續型的隨機變數。 (3) 一筆訂單的單位產能獲利是一個連續型的隨機變數。在這些隨機性的問題假設下,當一筆已知產能需求量及單位產能獲利的查詢訂單到達時,配合目前已知的剩餘產能,此決策模型可以去決定此筆查詢訂單應該接受或拒絕。而這決策模型稱之為動態隨機產能分配決策過程 ( Dynamic stochastic capacity rationing decision procedure, 簡稱 DSCR) 。

  此篇研究亦將洪 and 李 【 2007 】的 DSCR 法做三個不同的延伸: (1) 假設訂單的單位產能獲利及產能需求量為間斷型的隨機變數。 (2) 面對固定數量的訂單來到時,如何將此筆訂單定價,才可確保獲利最大化。 (3) 假設可以接受部分的訂單,當一筆查詢訂單來到時,製造商必須決定該接受的數量使得獲利最大化。最後模擬實驗顯示出在這三個延伸下,使用 DSCR 法確實可比其他方法得到更好的期望獲利。
本研究提出三種方法求解單一專案、作業不可中斷性的無限作業執行模式之資源限制專案排程問題,專案中每一個作業之作業強度在執行期間是不可變動且資源可重覆使用,目標在於最小化專案的總完工時間。我們提出片段線性曲線去近似作業執行時間與作業強度所構成的連續型非線性曲線關係,若專案排程問題利用片段線性曲線去近似非線性曲線關係,在本研究中我們稱之為近似問題。第一種方法:分枝窮舉法,能夠得到近似問題的最佳解,然而隨著問題大小的增加,分枝窮舉法的求解時間也會急劇上升,因此本研究提出第二種方法:集束搜尋法搭配 Boctor 【 1996 】演算法與吳【 2007 】線性規劃來求解本問題,希望能在合理的時間內得到一個不錯的專案排程解。但是對於大型問題來說,集束搜尋法仍然不夠有效率,故本研究提出第三種方法:複次 Boctor 演算法,能夠非常有效率的求解大型專案問題,但所求出的專案排程解也相對地較差。根據實驗與統計分析,我們可以決定集束搜尋法的控制參數,並比較三種方法的求解效率與求解結果。
本研究針對一個將需求區分為多等級的庫存配給問題下,探討如何維持庫存數量來滿足各式各樣的需求。當倉庫的庫存有限時,管理者傾向將庫存提供給等級較高的需求,而為了處理在供貨前置時間內所存在之不確定性因子,本研究提出了兩個方法對每一個來到的顧客進行滿足與否其需求之判斷,此兩個方法分別是動態隨機庫存配給決策步驟 (dynamic stochastic inventory rationing decision procedure) 以及風險水準庫存配給決策步驟 (risk level inventory rationing decision procedure) 。 此庫存配給問題的目標為在滿足任何等級較低的需求前,儘可能將庫存優先提供給等級較高的需求,同時在供貨到達前,我們也希望有能力來滿足等級較低的需求以避免庫存殘留的情況發生。根據模擬實驗的結果可知,風險水準庫存配給決策步驟較其他方法能最有效地提升最高等級需求的滿足率,而動態隨機庫存配給決策步驟可在維持最高等級需求的滿足率下,同時也能提升最高等級需求的滿足率。此外,有別於其他研究,本論文更能處理需求數量以及供貨前置時間為隨機變數之存貨系統,甚至在需求數量以及供貨前置時間為固定參數之存貨系統下,本論文提出之方法之績效也優於其他研究。
顧客滿意度的高低對企業來說舉足輕重的影響,它對於一個企業的成功扮演著關鍵的角色。本篇論文探討一二十四小時客服中心之人員排班問題。為了要使顧客的需求達到最大的滿足,我們的目標是要找出一最佳排班表來使所缺乏的人力資源量為最少。

在本篇論文研究中,我們希望能同時考量到客服中心擁有變動需求、每位客服人員所擁有的技能不同且並非唯一、政府相關法規限制的這些現實因素並由啟發式演算法在合理的計算時間內求得一不錯的解。採用四種搜尋法 ( 模擬退火法、塔布搜尋法、基因演算法、變動鄰近解搜尋法 ) 來求解客服中心之人員排班問題。透過建構一線性規劃模型來針對每一個時間區段的技能需求進行人力資源配給使得短缺成本為最小。最後進行電腦模擬實驗來評估應用四種啟發式演算法的績效。結果顯示在本研究問題中,模擬退火法相較於其它方法表現較好。
2007
近年來人力成本不斷提升,尤其客服中心的人事成本佔了總營運成本的百分之七十,因此客服中心的人員排班問題越來越為重要。

本研究提出兩個混整數數學規劃模型求解二十四小時營運之客服中心的長期排班問題,這兩個數學規劃可以求得問題規劃期間最佳的人員班別指派,數學規劃中所考慮的法規限制比起 過去以最佳化求解排班問題的研究,本研究所考慮的限制條件較完整。

過去求解人員排班問題或是客服中心之人員排班問題的文獻,所考慮的範圍大多都是在預測每個時間區段的人力需求數量以及每個班別應該安排的人數,只有少數的文獻有考慮人員的指派。過去考慮人員指派的文獻,大都是以啟發式演算法求解,非以最佳化演算法的方式處理問題。而且大部份之文獻都是分開來以兩個階段分別求解,一個求解每個班別應安排的人數,另一個將班別分配給特定的人員。分兩階段求解的缺點是可能找到的解和最佳解差距很大。為了避免分兩個階段求解,本研究用單一個數學規劃最佳化模式直接決定人員被分配的班別。

整數規劃的求解速度主要是受限於整數變數個數的影響,本研究提出一些新的數學規劃模式建制的技術,以減少整數變數的個數,並利用該建制的技術在本研究的數學模式二。期望數學模式二擁有比數學模式一更好的求解效率。

實驗驗證後,發現雖然數學模式二的整數變數個數比數學模式一少,但在固定求解時間下,數學模式一的解明顯比數學模式二好。
客服中心具有大幅度需求波動的特性。然而,由於人力成本的考量,以及政府法規與公司規定的限制條件下,要提供 100% 的服務水準來符合隨時間改變的需求 是不具經濟效益的。 本研究主要探討的是二十四小時客服中心人員排班問題,假設各客服人員效率相同且允許各人員擁有多重技能,並給定各班別類型、各時間區段人數需求、以前各人員排班資料等已知條件下,配合各項政府法規、公司內部規定與員工個人休假安排等限制條件,建構出一個客服人員排班問題的求解方法。

本研究的客服人員排班問題求解方法共分為兩個模組,第一個模組主要以限制規劃的方式將客服中心人員排班問題的模型建構出來,再以限制規劃特有的求解技術,一致性技術、搜尋演算法與限制繁衍機制等來搜尋所有的可行解。在第二個模組中,我們將人員排班階段求解出的班表結果,利用線性規劃的數學模式,分配人員到各時間區段中不同的技能需求。而此線性規劃數學模式中的目標是最小化技能需求的人力不足成本。

為了驗證本研究所提出的方法,我們將利用限制規劃軟體 ILOG Solver 去執行第一階段的運算,再利用線性規劃軟體 ILOG CPLEX 執行出線性規劃問題的結果。

最後,由實驗結果得知, 本研究所提出之方法可以求解出人員短缺成本最低之最佳排班班表。但是當問題範圍增大時,限制規劃求解的困難度也隨之增加。因此,期望這項問題可以作為未來研究限制規劃求解人員排班問題的一個改進方向。
本研究主要探討 可變作業強度 (variable activity intensity) 之 資源限制專案排程問題 (resource constrained project scheduling problem with variable activity intensity) 。此 問題之特性在於 專案中之作業其資源耗用率為可變動的,當一個作業的資源耗用率愈高,其作業時間愈短,也愈快完成,資源耗用率與作業強度呈正比的關係。 “ 作業強度 ” 一詞乃由 Hackman and Leachman 【 1989 】根據 Leontief 生產函數理論所衍生。而 Leachman et al. 【 1990 】應用 Leontief 生產函數理論提出作業強度與作業時間呈倒數關係及作業強度與資源耗用率呈正比關係。因此,作業強度可建立作業時間及資源耗用率的關係並應用於資源限制專案排程問題。

近年該類範疇之研究文獻甚少,除了使用非線性規劃 (nonlinear programming) 或混整數規劃 (mixed integer linear programming) 表達問題之外,並未提供測試問題,因此無法得知文獻所提方法求解問題之效能。本研究主要利用線性規劃模式建構問題,並產生測試問題探究本方法求解結果與成效。

使用線性規劃遭遇的困難有二:第一,作業強度與作業時間呈非線性之凸函數 (convex) 關係,因此本研究將使用片段線性曲線 (piece-wise linear curve) 近似作業強度與作業時間呈非線性之凸函數關係;第二,專案有很多組可能事件順序,事件順序的不同會產生不同的資源限制式,本研究提出一個系統化的方法求解問題。首先建構一個計算方法搜尋專案所有可能的事件順序,有了片段線性曲線及一組事件順序即可建構一個線性規劃問題,比較所有事件順序所產生之線性規劃之目標值即可得出問題的近似最佳解。
2006
彩色濾光片的三原色(RGB)製程中,利用相同的平行機台經過裝設後可以生產多種不同規格的產品,而每種產品 皆須在平行機台上回流三次以上才能完成此製程。本論文針對三原色製程的生產排程問題作研究,因為排程的目的為及時滿足後端製程的需求,所以將目標函數定為 使所有批次產品的總延遲時間(total tardiness)最小。在求解問題時考慮了產品需求率隨著時間而變動、不同的作業間具有順序相關的裝設時間、產品以批量方式進行製造等生產特性。

 求解這個生產排程問題時,本論文使用賴[2005]提出的二階段式解法,並對其解法做了部分修正,以考量隨著時期而變動的產品需求率。第一個階段,利用 經濟訂購批量模型(EOQ Model)求出合適的批量大小,決定在規劃時間內所有待加工的批量,一個批量即為平行機台排程問題的一個工件。第二個階段,先利用ATCS (Apparent Tardiness Cost with Setups)派工法則排出工件在平行機台上的加工順序,再以此作為起始解,用搜尋演算法尋找較佳解。本論文對三種搜尋演算法進行比較,分別是模擬退火法 (Simulated Annealing)、塔布搜尋法(Tabu Search)及模因演算法(Memetic Algorithm)。模擬退火法的鄰近解採取隨機方式產生,塔布搜尋法的鄰近解則設計了一個半隨機的方式產生,模因演算法的鄰近解依照基因演算法,採取 交配(crossover)和突變(mutation)的方式產生。

  最後,本論文的計算實驗中列出了數個因子,討論其對總延遲時間的影響。發現規劃時間、搜尋法、機台數目、產品種數這四個因子皆對最終的總延遲時間有顯著的 影響。在排程環境的設定方面,較短的規劃時間、較多的機台數、較少的產品種數皆有助於降低總延遲時間。至於所使用的搜尋法,本實驗顯示半隨機式鄰近解的塔 布搜尋法明顯優於其他兩種搜尋法。

在半導體製造業中,有關等候時間限制(Queue Time Limit)的研究不多,本論文研究方向在於有等候時間限制的放行控制法則 – 模擬控制法則 (Simulation-based Control Rule)、等候線估計控制法則(Queue Estimate Control Rule),兩種控制法則針對在不同的等候時間限制、不同的產能水準下,是否能夠減少批量重工次數、提高產出率。完全放行法則(All Release Rule),則是用來做為在等候時間限制下,沒有使用控制法則的情形,做為有使用控制法則的對照比較。

 模擬控制法則是由涂 [2005] 提出,對於有等候時間限制的批量放行與否,用模擬的方式評估,即建立一模擬環境與實際環境完全相同,對於被評估之批量能在模擬環境中的不超過等候時間限制,才允許此批量在實際環境中放行以進行加工。

 等候線估計控制法則,是由Leachman [1988] 所提出的等候線管理(Queue Management, 簡稱QM)的觀念而得。Leachman的等候線管理是以工作站觀點來計算等候線長度隨時間變化的情況,而本論文所提出的等候線估計控制法則,則是以批量 的觀點,計算批量在途程上的各工作站,在批量抵達的時間點,計算其工作站等候線長度的估計,藉此來判斷此批量在此等候時間限制的條件下,是否該進行加工。

 本論文研究目的在於利用等候時間限制下的放行控制法則(簡稱為控制法則),使批量尚未投入加工時,即可預測批量是否能在等候時間限制之內被加工,藉此降 低批量重工次數以及提高單位時間的產出。經實驗分析,完全放行法則在各種等候時間限制之下,當投料量漸增時,批量重工次數也隨之增加。模擬控制法則在各種 等候時間限制之下,在高投料量時,批量依然可以維持在低重工次數。等候線估計控制法則,在等候時間限制較短的情況,其表現略優於完全放行法則,在等候時間 限制較長的情況,其表現則接近模擬控制法則。

2005
本論文針對彩色濾光片生產過程中的RGB製程進行批量排程(Lot sizing and Scheduling)的研究,在RGB製程的環境當中,生產多種不同的產品,每台機台都可以做相同的工作,不同作業需要裝設時間且為順序相關的裝設時 間,每種產品經過此製程皆須回流三次以上。

 針對此困難的排程問題,本論文提出一個兩階段啟發式演算法,第一階段中,將本問題的生產環境做適度的修正,滿足EOQ模式求解的條件,利用EOQ模式將 已知的參數代入公式中求解批量大小,並檢查批量大小是否合理,如果發生不合理解時,將週期長度放大到一個生產週期閒置的時間剛好等於估計的總裝設時間,利 用重新修改的週期長度得到合理的批量大小。第二階段中,將每批的產品看成一件工作(job)利用ATCS派工法則,只要平行機台中有任一機台閒置即計算未 排程表單中所有工作的優先指標,選取最大的優先指標進行加工,如此循環直到未排程表單中沒有工作為止,即可得到排程解。如果有兩台以上機台同時閒置,則隨 機選取其一。

 為了驗證求解品質,我們進行實驗設計並以總延遲時間為績效指標來比較十二個兩階段方法,這十二個兩階段方法是由EOQ和固定批量這兩 個批量方法與ATCS、ATC、COVERT、EDD、FCFS和MOD_ATC這六個派工法則組合而成的。經由實驗結果可知,EOQ+ATCS和固定批 量為200+ATCS表現最好,但是利用EOQ來決定批量大小有一定的公式求解,而固定批量大小卻必須利用試誤法不斷的嘗試才能找出一個較佳的批量大小, 因此本論文提出的方法不僅僅方便使用且解題成效也不會比較差。

產能規劃是生產決策者決定要有多少數量的機器設備來提供產能,生產所需數量的產品。由於產品需求的不確定性,使得產能規劃的工作更為艱難。本文針對 多規劃時期下,多產品種類、多機器種類、不確定需求下之產能規劃問題以兩種方法求解並比較其結果。此兩種方法的目標式皆為欠貨成本加上機台購買成本之最小 化,限制式則包含產能與預算的限制。

 本論文把未來的需求模式化為以好幾套的需求劇本 (demand scenarios)所組成的集合,並對每一套劇本指定其發生機率。第一種方法將此問題模式化為隨機規劃模型並求解之。第二種方法將問題模式化為需求固定 的混合整數規劃模型,接著,再將此模型配合決策樹的架構來模式化需求的不確定性並求解之。

 本論文的實驗把兩種方法求得的成本,分別計算在不同需求劇本下與完美資訊期望值的差距百分比。實驗結果顯示,隨機規劃與完美資訊期望值在不同需求劇本下的差距較小,求解的時間也比決策樹分析方法快。

車輛巡迴路徑問題(vehicle routing problem, VRP)在物流管理中是非常重要的一個問題,其目標函數多為最小化車輛行駛路徑距離與配送車輛數,以減少企業在實體配送方面的運輸成本,隨著現實環境的變 遷,越來越多的限制式也增加了車輛巡迴路徑問題的解題複雜度。  

 距離第一個VRP的提出已經四十多年的時間,許多學者提出不同的求解策略,其中兩階段法(two-phased method)也常用來求解VRP,第一階段以簡單的啟發式解法求得初始解路徑;第二階段再針對初始解予以改良品質。本論文解決多場站、多趟次VRP,利 用貪婪法(greedy algorithm)求出初始解,再根據Skitt and Levary 【1985】將多場站、多趟次的車輛巡迴路徑問題,建構成一線性規劃問題,在線性規劃中以行(column)來表示路徑,並且使用行產生法(column generation),另行建構一整數規劃子問題來產生新的路徑以改善解。  

 本論文實際求解出不同大小規模的問題,並且與Skitt and Levary實作的結果作比較,進一步分析本論文應用行產生法的解題效率及品質。

2003
在生產環境中,一套成功的排程系統是以追求降低存貨成本與欠貨成本為目標,然而面對隨時間改變之需求的情況,其批 量生產決策卻有困難之處。本論文面對彩色濾光片平行機台的產能受限批量排程問題,考量真實生產環境中會遭遇的問題,追求降低各機台間存貨量過大的狀況,同 時避免欠貨發生,建立一套有效的生產排程方法。本論文的方法是將問題分解成為數個單階的子問題,將後一個階段之生產排程所決定的輸入物料數量做為前一個階 段的物料需求數量。面對每一個子問題,本論文建立一套啟發式演算法。為了反應需求率隨時間改變的特性,將生產時期以避免高估產能的方式分割為數個分割時 段,依據Leachman所提出的存貨耗盡時間成本決定起始生產順序。並使用「交換」與「併入」的方式調整生產順序,同時修正解的合理性,適當的計算總成 本值,使批量生產排程能夠盡量降低存貨、欠貨及裝設成本。重複以上步驟,希望能夠快速得到一個令人滿意的合理解。

 由實驗中得知,只要決定適當的分割時段數,本演算法就可以針對各個產品很有效率地找出一條很貼近需 求曲線的生產曲線,降低存欠貨以及裝設成本。較長的分割時段長度會有較佳的最終排程解,但是比較耗時;而較短的分割時段長度則能較快速求解,而解仍是令人 滿意的。透過實驗結果我們建議分割時段長度的設定應該約為平均裝設時間的2~3倍。

一般生產規劃為了使問題簡化以快速求解,通常不考慮裝設時間及裝設成本。為了使生產規劃更符合實際的問題,本研究 將裝設時間及裝設成本予以考慮在內,將問題建構成混合整數規劃(mixed integer programming)模型,使得批量問題的求解成指數型困難問題(NP-Hard)。因此發展啟發式的演算法來改善尋找最佳解的過程。  

 近年來有一些啟發式的演算法發展出來,被廣泛的運用在求解指數型困難問題,且常被用來解困難的最佳 問題和排程問題,其中以塔布搜尋法來求解問題,大都能得到很好的結果。本論文針對多項產品、多種資源、多生產時期,且包含裝設時間與裝設成本的生產規劃問 題進行探討,利用塔布搜尋法的技巧求解。此外,提出新的候選列表策略改進塔布搜尋法,利用線性規劃簡捷法(simplex algorithm)所提供的後尋優資訊,排列鄰近解的順序,使得有高順位的鄰近解有較高的機率為目前最優解,利用排序後的候選列表來減少對鄰近解的搜 尋,以加快求解速度。      

 利用不同的參數值設計不同類型的隨機問題,由各演算法進行求解來分析演算法求解的品質,並分析演算 法求解的速度,最後對各種演算法進行實驗結果比較。      

 經由實驗的結果,本論文提出的演算法其求解的品質與傳統塔布搜尋法差距不大,但在搜尋的時間方面縮短了許多。因此,對於生產規劃含裝設問題,本論文所提出的演算法是一套相當良好的搜尋法則。

簡單塔布搜尋法(simple tabu search)是一種區域搜尋法,被廣泛的用於求解各種排程問題上,但是塔布搜尋法的鄰近解設計在求解零工式生產排程問題(job shop scheduling problem)時,會有錯失較佳解的情形,原因來自於通常在產生鄰近解時,都使用交換法將現行解中的工件順序交換產生新的解,但若有一個鄰近解N,N的 目標函數值並不好,因此塔布搜尋法並不會將解移動到N,但是N的鄰近解N’是一個較佳的解,只要塔布搜尋法將解移到N上,就可以發現比目前解要佳的解 N’,但是因為塔布搜尋法鄰近解的設計,造成短視近利所以並無法發現這一個較佳的解N’,我們希望藉由修改塔布搜尋法的鄰近解設計來克服這個問題。  

 Nowicki and Smutnicki [1996]提出一個改良的塔布搜尋法,名為快速塔布搜尋法,該方法改進簡單塔布搜尋法,將鄰近解的個數有效的減少,對於裝設時間為順序獨立 (sequence-independent)的零工式生產排程問題有很好的效率並能獲得品質十分優良的解,Demirkol and Uzsoy [1998]提出例子說明快速塔布搜尋法並不適用求解裝設時間相依(sequence-dependent)的零工式生產排程問題,因快速塔布搜尋法的鄰 近解設計會錯失許多較佳的鄰近解。      

 因此,我們希望由探討及改進鄰近解產生的方法讓其在求解相依裝設時間的零工式生產排程問題時能夠找 出品質更好的解。      

 最後我們藉由實驗設計評估各搜尋法的搜尋能力,實驗結果顯示經過改良的多步式塔布搜尋法有比單步式塔布較好的跨越區域最佳解的能力,同時搜尋能力也稍優於單步式塔布搜尋法。

Nowicki and Smutnicki【1996】提出的快速塔布搜尋演算法,在定義鄰近解的移動為:「令 和 為某種機台上連續的兩項作業,且 和 在某條要徑上,鄰近解為將 和 此兩作業進行交換」,快速塔布搜尋法可以在不影響求解目標值正確性的情況下,大幅降低了鄰近解解集合的空間,因此可在很短的時間內求出零工式生產排程問題 之較佳解。  

 彈性零工式生產排程問題與零工式生產排程問題最大的差異處在於彈性零工式生產排程問題中各個工作中 心擁有平行機台的特性。因此在零工式生產排程問題上表現成果優良的演算法無法直接套用在彈性零工式生產排程問題上。      

 本論文結合塔布搜尋法、快速塔布搜尋演算法、以及本研究提出的要徑優化演算法,希望找出適用於求解 彈性零工式生產排程問題的啟發式演算法,並在合理的時間內找出較佳解。      

 實驗結果顯示,本論文所提出的演算法適用於求解較大的彈性零工式生產排程問題,並可在合理的時間內,求得優良的解。

半導體技術不斷的進步,各半導體製造廠商的製程技術都往更精密的製程研發,晶圓測試所扮演的角色也就更顯得重要, 因為新技術剛開始發展之時,都會有較低而且較不穩定的良率,在這一段期間內,快速準確的完成晶圓檢測的工作,有助於新技術的改良與發展,經過一段時間技術 的改進及製程的熟悉之後,才能夠逐漸地獲得穩定及較高之良率。  

 因為晶圓測試對半導體製造的重要性,所以成了本研究的重點。不過半導體製造有兩個階段的測試,第一 次是在晶圓製造完成之後的晶圓針測(wafer probing),第二次是封裝後的測試(final test),我們研究的重點著重在晶圓針測,如何在顧客所要求的時間內準時的交貨,並且使機台的工作負荷時間縮短,達到更大的產出,這是我們想要達成的目 標。      

 面對這樣的問題,可以利用混合整數規劃(mixed integer programming)將問題模式化,再利用演算法或是套裝軟體來求解問題。不過,模式的大小(變數與限制式的個數)會影響問題求解的速度,本論文提出 一種使用較少限制式與變數的數學模式。利用數學規劃軟體來求解時,希望我們的模式能夠減少求解的時間。在實驗設計的階段中,我們希望能隨機產生不同的問 題,來驗證我們的模式是否有較佳的效率。實驗的結果顯示本論文的模式確實能在較短的時間內求出最佳解。

模擬退火法(simulated annealing)的構想源於金屬冷卻結晶的過程,是一種常用於求解最佳化問題的啟發式演算法。而為了提升演算法速度,平行運算(parallel computing)被應用在演算法的設計架構中,使得能在更短的時間內能得到解答。  

 許多平行模擬退火法之理論依據為多向試驗(multiple trials),利用同一時間探索更多方向的試驗來拓展搜尋的廣度(breadth)或深度(depth),不進行溝通的分工模擬退火法(the division simulated annealing with no communication)以及叢集模擬退火法(the clustering simulated annealing)皆為平行化的模擬退火法,前者定義為各個處理器針對各自的起始解進行搜尋,產生各自的搜尋序列(search sequence),在搜尋過程中處理器不進行任何溝通,各處理器僅針對自身之目前解進行搜尋;而後者定義為讓所有處理器針對同一目前解進行運算搜尋各自的可能解,並各自決定其產出解之接受機率,最後根據事先決定之規則進行溝通比較,挑選其中一個可接受解取代目前解。      

 動態平行模擬退火法(dynamic parallel simulated annealing, DPSA)是合併不進行溝通的分工模擬退火法與叢集模擬退火法,並保留其各自的優點。在溫度高時,處理器各自執行各自的搜尋序列,增加搜尋的廣度。在溫度低時,將搜尋績效低的處理器合併成叢集,並針對共同目前解做搜尋,以拓展搜尋的深度。      

 本論文的重點在於定義動態平行模擬退火法中兩種演算法間之轉換時機,我們期望這將會提升模擬退火法的運算效率,而就針對規模較大的問題以及較長的運算時間而言,本論文所提出的二種平行模擬退火法的確是較獨立的模擬退火法有著更好的運算效率。
2001
及時生產系統(Just-in-Time)是以追求低存貨成本為目標的生產模式,但在一個動態需求的生產環境其批 量生產決策卻有其困難之處,所謂的動態需求是指需求速率會隨時間而改變。本論文考慮動態需求環境下的單一機台(single machine)產能批量排程問題(capacitated lots size scheduling),以最小的存貨成本為目標,希望能找出符合即時生產系統概念的生產排程。本論文主要的做法乃是將生產決策分為「離散決策」與「連續 決策」兩類。離散決策包含有各批量所欲生產的產品種類、各批量開始生產時期與結束生產時期。連續決策則為各批量精確的開始生產時間點與結束生產時間點。求 解方法為先利用塔布搜尋法或模擬退火法找出離散決策,再帶入一個以最小化總存貨成本為目標的數學規劃模式,以求解出連續決策的值與目標函數值。如此不斷地 重複以上步驟,希望可得到總存貨成本較低的批量生產排程。  

 由實驗中得知,本演算法可以很有效率地針對每一種產品種類,找出一條很貼近需求曲線的生產曲線,降低總存貨成本,並避免缺貨情況的發生。至於搜尋法則的搜尋成效部分,塔布搜尋法在搜尋最優解的成效比模擬退火法快且有效率,因此,建議使用塔布搜尋法搜尋新的離散決策。

目前台灣多數半導體公司皆已擁有一個以上的晶圓廠,而在現行制度下,各晶圓廠間之產能借調是由相關晶圓廠自行協商 調度,故易受到許多主觀性與非技術性的因素影響而使產能支援程度大打折扣。因此本研究的目的為針對多廠區之半導體製造公司的各晶圓廠間產能支援作業,建立 一套系統性的方法來求解出一組整體性產能支援方案,以期在維持每個晶圓廠各自營運以獲取本身最大利潤的經營模式下,達到兼顧提高整體公司生產與獲利的目 標。  

 本研究以Hung and Leachman [1996]所提出的線性規劃生產計劃模型為基礎求解各單一晶圓廠在其產品需求與產能限制下的最佳生產計劃,然後從最近的生產計劃期開始檢視所有晶圓廠在 該計劃期下之各種資源(如各類加工機台等)的產能缺乏與剩餘狀況,並針對該期之產能不足資源項目尋找對應於不同廠間之相同計劃期與同類資源的可行產能支援 來源。逐期解決各計劃期的各項產能支援作業,直到所有計劃期的產能不足資源項目都完成可行產能調度為止。      

 實驗分析結果顯示,本研究提出之產能支援方法不但在改進獲利方面的效果頗佳,且具有方便使用及快速 求解的優點。本方法平均可提昇整體公司獲利8.7%,並改善與最佳獲利間的差距程度達80%以上;在不限定最小產能移動量時,利用本方法可求得最佳整體生 產計劃的比例超過35%。而應用於規模愈大(晶圓廠數愈大)以及晶圓廠間產能差異愈大的問題時,可提昇及改善獲利的程度也愈高。另外,應用本研究方法尋找 產能支援方案的平均求解時間約為一分鐘,其中小型問題(晶圓廠數小者)的平均求解時間不超過10秒,較大型問題的平均求解時間亦不超過三分鐘。因此本研究 方法可以有效應用於多廠區半導體製造公司,以更客觀且有效率的規劃各廠間的產能支援作業,並獲得更佳的成效。

2000
供應鏈的體系中若要能夠達成最佳化,只有將各環節緊密地連結在一起,以便滿足顧客的需求,以最適合的品質、最有效率的交 貨方式,在適當時間將適量的貨物交到顧客的手中。由於,供應鏈中每一環節都有其生產計劃,當其中一個環節需要供應鏈中別的環節來提供生產原料時,也許會因 其彼此生產計劃所規劃的產品組合不同而無法完全吻合,喪失獲取最大利潤的機會。

 因此,本研究主要是建立一線性生產規劃模型,假設上下游製造廠皆使用此一規劃模型,並以下游製造廠的立場 為出發點,來針對如何讓供應鏈中上下游製造廠的生產計劃緊密結合之主題加以探討。即當市場需求大過公司所能生產時,藉由結合上下游製造廠的生產規劃模式, 並根據市場需求的產品組合,利用給予上游製造廠的採購價格來當作一誘因,來調整上游製造廠的生產計劃。也就是說當上游製造廠所提供的產品組合不能配合下游 製造廠需要時,透過本研究所提出之價格更新模組來改變給予上游製造廠更優惠之採購價格,並藉由不斷遞迴方法來重解上下游製造廠之生產計劃模型,使供應鏈中 成員的生產計劃可以更加緊密結合,以求算出下游製造廠利潤較佳之產品組合,而上游製造廠亦可獲得較優惠的採購價格,來同時達到彼此雙贏的局面。由實驗分析 中可知,本論文所提出的線性生產規劃模型與價格更新模組,可以使上下游製造廠的生產計劃配合的較緊密。

在 Hackman and Leachman [1989] 所提出的通用生產模型中,對於非整數箝制時間 (leadtime) 非等長規劃期間 (planning periods) 的問題所建構的離散模型 (discrete model) 雖然是正確的,但是所求得並非真正的最佳解。在本論文中我們證明出當延遲時間為整數的模型中若採用所有延遲時間的最大公因數作為時間單位及規劃期間長度, 則此模型可以求得真正最佳解,但是如此會使問題大小會迅速擴大,因而需要很長的求解時間。為了能夠在合理的運算時間內求得真正的最佳解,本論文針對離散模 型發展出一套變數分割程序,希望能夠藉著變數的分割以增進目標值。變數的分割原則是在考慮產品存貨平衡以及資源產能限制下所發展出來的。分割方式是將原有 的生產變數在原來的規劃期間內的某些時間點一分為二,藉此讓生產速率變數能有彈性地變動以達到提高目標值的目的。從實驗分析得知,經由本論文提出的變數分 割程序可在不造成問題大小迅速擴張的情況下有效地提高目標值,而且其中一種變數分割程序可以得到真正最佳解。
一般的批量問題在考量裝設決策時,經常以 生產時期為規劃的單位,而忽略跨週期生產的情形;然而,實際生產環境大多數產品的生產皆可有跨週期生產。為了使批量問題更接近實際情形,我們將跨週期生產 考慮在批量問題內,使成為單一機器種類、多機台、多產品、多生產週期、並包含裝設時間、裝設成本、跨週期裝設的混合整數規劃問題,其提供裝設決策 ( 二元整數變數 ) 及批量大小 ( 一般實數變數 ) 兩種決策。由於這樣的問題模型會使得求解時間形成指數型困難 (NP-Hard) ,我們嘗試利用新的演算方式來改善尋找最佳解的過程。

 近年來,有不少研究是利用塔布搜尋法及模擬退火法來求解困難的最佳化問題和排程問題,在和其它現有的經驗法則比較下,大多能得到很好的結果,本篇論文針對跨週期裝設之批量問題,分別利用塔布搜尋法及模擬退火法,提出七種啟發式搜尋法則,以求得較佳的解答。

 經由實驗的結果,在絕大部分的問題上面,啟發式搜尋法則求解的時間遠小於利用分枝界限法求解的時間,而且 利用評估值模式的速移塔布搜尋法無論在搜尋時間、搜尋解品質上皆有最佳的表現,因此,對於求解含跨週期裝設的生產計劃問題,速移塔布搜尋法是一種相當良好 的啟發式搜尋法則。

本論文主要在探討靜態隨機的非等效平行機 (unrelated parallel machine) 排程問題。其中考量工件加工時間的隨機性 (stochastic) ,且假設工件在機台上的加工時間為常態分配,亦即平均值 (mean) 與變異數 (variance) 均為已知。在交期已知下,本論文將以工件平均期望延遲時間 (average expected tardiness) 為績效指標。利用此績效指標,在求解不確定性加工時間問題時所需的計算時間並不會比確定性問題多出甚多。在求解方法上,本論文將先比較六種起始解的產生方 法,並將其中表現最好的方法來得到一個初步的排程,並以此排程來當作搜尋法的起始解。接著針對非等效平行機台問題的特性,本論文嘗試利用四種啟發式搜尋法 來作求解,分別為塔布搜尋法、遺傳演算法、模擬退火法與改良遺傳演算法,並利用一些搜尋參數的計算,以期望減少求解的時間與提高求解的品質。

 由起始解方法的實驗結果可知, ATC 法則的表現最佳,因此本論文將以 ATC 法則產生各個搜尋法的起始解。接著經由搜尋法的實驗分析得知,在不同 CPU 時間下各種演算法的解題優劣稍有差異,但綜合來說,利用資訊縮小鄰近解集合的塔布搜尋法解題成效最佳,以遺傳演算法表現最差。

由於中央處理器昂貴,一般測試機台上會有多個測試頭,以減少中央處理器的閒置時間。而多頭測試機台由一個中央處理器負責多個測試頭執行測試,每一個測試頭 上可能有相異的測試產品,因此多頭測試機台上會有不同的產品組合,而產品組合會影響加工時間。本論文針對多頭測試機台此一特性及裝設時間的相依性 (sequence dependent setup times) 及完成時間與交期的差異,提出狀態變數及批量變數,且使用這些變數來修改塔布搜尋法、模擬退火法及遺傳演算法的搜尋過程,並使用這些方法求解多頭測試機台 的最小化平均延遲時間 (average tardiness) 排程問題。在各搜尋法開始搜尋時,使用 Apparent Tardiness Cost with Setups (ATCS) 派工法則將產品排入所有測試頭,將得到的結果當作各搜尋法的起始解。最後經由實驗設計與分析,發現利用評估批量變數後採用固定選取法的塔布搜尋法無論在短 期、中期或長期的搜尋時間點,其搜尋到的最佳目標值皆優於其它本論文提出的搜尋法。因此本論文認為利用評估批量變數後採用固定選取法的塔布搜尋法是一種比 較有效率求解本問題的搜尋方法。
1999
在現行物料需求規劃( MRP )系統下,由於生產計劃時欠缺產能限制的考量,生產計劃常須經過反覆地調整才能變得可行,又因批量大小決策( lot sizing decision )與產能需求規劃( capacity requirement planning )沒有同時進行,更使裝設決策( setup decision )變得困難。此外,在實際應用時,生產計劃需考量多種等級需求,如何安排有限資源產能以滿足不同等級的需求,也是生產計劃的重點。本研究提出一個可規劃多 種需求等級、考慮機器產能限制、裝設時間( setup time )、裝設成本( setup cost )與前置時間( lead time ),並適用於一般性產品結構( general product structure )的生產計劃模型,其可將原 MRP 系統中之『主生產排程』、『物料需求規劃』、『產能規劃』與『批量大小決策』四者整合於單一生產模型中,使生產計劃的可行性與便利性提高。本生產模型中包 含數個需求等級的問題,每一個需求等級的問題屬於一個混合整數規劃( mixed integer programming, MIP )問題,依序求解各 MIP 問題,便可獲得一個既可行又能提高獲利的生產計劃。

 本論文使用塔布搜尋法( tabu search )、適應式模擬退火法( adaptive simulated annealing )與適應式遺傳演算法( adaptive genetic algorithm )求解本生產問題。經實驗分析後得知,在不同需求等級、不同 CPU 時間下,三種演算法的解題優劣稍有差異,但綜合說來,塔布搜尋法的解題成效最佳、適應式模擬退火法次之,適應式遺傳演算法最差。

在複雜的供應鏈管理研究領域裡,訂單管理是一項基本的活動,而其中訂單查詢則是現今之研究所忽略的。若擁有快速而有效率之顧客訂單查詢的回應能力,則企業將能在顧客服務方面獲取更強勢的競爭力。

 目前一般公司對於顧客的訂單查詢內容,必須經過其內部各相關部門的開會協調,確認了訂單承接總量 後,再以人工處理的方式來計算產能以及訂單之相關交期資訊,以至於回覆顧客時往往已耗時數日乃至於一週。若再加上供應鏈之傳遞效應的影響,則由零售商端點 上傳至供應商端點的需求查詢資訊,其傳遞時程勢必更延長到一個月以上。由於目前商業環境的競爭益趨激烈,產品生命週期短暫,任何的時間因素都必須加以嚴格 控管,所以如此的訂單查詢回應能力將嚴重延誤商機而使其喪失市場競爭力。

 本論文是以半導體晶圓廠為研究對象,利用現有 Leachman [1992] 所提出之生產計劃模型為基礎,透過線性規劃中敏感度分析的方法來重解原生產計劃模型,產生新的可應允數量,並應用現今電腦系統快速而大量運算的能力,構建 一個能即時且電話中提供相關決策資訊的訂單查詢管理系統,以精確而快速的回應顧客之訂單查詢需求。

 經由實驗之驗證,本論文所建立的訂單查詢管理系統,能夠於很短的反應時間內快速而有效率的運作,達 到即時回應顧客的基本要求。另外,由於交貨排程計劃詳盡的規劃其需求產品之交貨排程,能使顧客進一步精確的規劃其細部之生產計劃或銷售計劃,更提昇了公司 於顧客服務方面之競爭力,以及供應鏈之整體的運作效率。

Leachman 與 Carmon 【 1992 】提出的可替代機器產能負荷問題的線性規劃方法,這個方法使得具有再重覆製程與可替代機器的複雜生產程序,可以利用線性規劃計算生產計劃。而在目前的生產 環境中,可替代機器與再重覆製程的生產特性已經越來越常見,尤其是半導體產業。然而這個方法中有兩個問題點,第一個問題點是模型中所使用的「均勻假設」, 也就是說可替代機器在加工其共同能加工的生產步驟時,彼此的加工時間必須呈固定比例,然而在實際工業的問題中,這個假設對某些實際工業生產卻未必成立;而 且這個方法利用不斷聯集具有共同機器的可替代機器集合,增加模型中的產能限制式,這個聯集程序會增加模型中的產能限制式,可能會增加求解線性規劃問題的時 間。為了解決這兩個問題,本論文混和 Leachman 與 Carmon 【 1992 】所提出的觀念提出一個混合模型,並且利用實驗比較混合模型與 Leaman 與 Carmon 【 1992 】所建議的模型之間的差異。混合模型在產生產能限制式的時間與記憶體方面較直接產品組合法為佳,但在最後求解線性規劃模型所需要的時間方面則是直接產品組 合法較好。
本論文在研究半導體後段製程測試機台的排程問題。測試機台分為中央處理器( CPU )及測試載具( testing handler )兩個部分。多頭測試機台( multi-head testing machine )是為了降低中央處理器的閒置時間,以一個中央處理器連接多個測試頭。多頭測試機台問題近似於平行機台的問題,差別的是在同一台測試機器上,各測試頭的產 品組合將會影響產品的加工時間;如此的問題特性提高了解題的複雜度,所以將嘗試以改良的搜尋法解決本問題。

 本論文的目標是降低待測產品的最大完成時間( makespan )。解題方法將分為兩個階段,第一階段將提出一個創新的啟發式甘特圖演算法來快速的得到一個有效的解,並當作下一階段的起始解。第二階段改良塔布搜尋法, 模擬退火法以及遺傳演算法來搜尋此排程問題的最佳解。為了增加解題的速度,塔布搜尋法將以適合本問題的方法來縮小鄰近解集合。而遺傳演算法也將採用適合本 問題的配對方法來進行搜尋。最後,將以實驗設計的方法來比較這一些演算法對於本問題的表現優劣,並建議一個最適合本問題的演算法。本論文期望能找到快速且 有效的演算法來求解多頭測試機台的問題,並能應用在現場的生產管理中。

本論文針對半導體晶圓廠黃光區的排程問題,期望透過一種持續的搜尋工具能夠在即時的環境下提供有效的排程。實際環境下的各種因素包括:機台當機、光罩限 制、製程限制、光阻液限制、裝設問題等等限制與不確定因素都列入考量。本論文使用三種搜尋法:塔布搜尋法、模擬退火法以及遺傳演算法,並以實際的問題對三 種方法進行比較。另外,我們還針對即時排程提出了一種敏感搜尋法(Sensitivity search),期望能透過此種方法提高搜尋法的效率,突破搜尋法耗時太長的限制,使得敏感搜尋的方式能在現實環境中排程問題不斷改變的情況下,提供更即 時的排程。而藉由實際晶圓廠提供的資料所得到的實驗結果顯示,敏感搜尋法的確能有效的提高搜尋的效率,而在本問題中,塔布搜尋法在三種搜尋法中的表現最為 突出。
在競爭激烈的半導體產業中,企業的存貨成本愈低可以相對降低製造成本,所以改善存貨政策是提升企業競爭力的利基之一。本論文以存貨管理的觀點研究半導體廠 庫存料件的分類及特性,討論如何應用五種不同的存貨模型於不同的半導體庫存料件上。本論文依據不同的半導體庫存料件找出適合的存貨模型,並以最小化存貨成 本為目標以計算各類庫存料件的理想存貨水準,並以近似的資料作例子去說明其應用。
1998
本研究為了使生產規劃更接近實際的生產問題,將裝設時間、裝設成本,均予以考慮在內,但因為加入此裝設決策後,問 題模型便成為混合整數規劃( Mixed Integer Programming )問題,使批量問題的求解成指數型困難問題( NP-Hard )。所以,嘗試以新的演算方式來改善尋找最佳解的過程。

 由於近年來有不少的研究是利用遺傳演算法來解困難的最佳化問題和排程問題,在和其他現有的經驗法則 比較下,都能得到很好的結果。所以本篇論文針對多項產品、多種資源、多生產時期,以及含裝設時間、裝設成本的生產規劃問題作探討,提出利用遺傳演算法的技 術以及一個啟發式的運算子,來排序鄰近染色體的集合,再從中找出優良鄰近染色體,以幫助求解的過程,使問題能得到最佳之解答。

 藉由設計決定配對方式的實驗,比較本論文中所發展的四種配對方式,找出何種配對方式,對於求解時較有助益。再設計解題參數的實驗訂出 解題參數值,設計不同題型的隨機問題進行因子變動對演算法的影響,最後將演算法的結果與分枝界限法的最佳解以及其他啟發式演算法的解進行實驗結果比較。

 由本論文所提出的演算法,可以得到以下的結果: 1. 較其他啟發式演算法更逼近最佳解。 2. 由實驗結果可以評估出本演算法的適用性。 3. 和傳統解法相比較,演算法對於解大型的問題時,能有效減少求解的時間。所以本論文中的演算法可以更正確的找到或逼近最佳解,即與最佳解的差異比其他演算法 小,而得到相當不錯的結果。

在中長期的生產計畫中,最常採用的方法是利用 MRP 來做規劃,但對半導體製造而言由於生產步驟複雜,若要使用 MRP 來做生產計畫將會造成嚴重的誤差,故 Leachman[1986] 曾討論過 MRP 並不適用在半導體的原因,並針對整個半導體製程提出一完整的規劃方案,其中對晶圓處理製程的產能利用,提出產能負荷模組 ( capacitated loading module) ,根據產品的需求,以線性規劃 (linear programming) 的方式,來分配機器的產能,並決定每期每種產品的投料量。

 在產能負荷模組中,透過時程參數 (cycle time) 來推導動態生產函數 (dynamic production function) 的系數,而時程參數為一隨時間變動的參數,隨著投料計劃的不同而有所變化。在該模組中,使用歷史資料來產生平均的時程參數。但是未來投料計畫和歷史的投料 計畫並不一定相同,故工作站產能負荷會隨時間改變,導致批量在工作站前的等候時間會隨時間改變,故時程參數亦會隨時間改變。針對此一問題, Hung[1991] 使用產能負荷模組產生的投料計劃,模擬其生產過程,從模擬中蒐集新的時程參數,再將新的時程參數代入該產能負荷模組,求解新的投料計劃,如此重覆迭代,來 觀察時程參數的變化,結果發現產能負荷模組所使用的時程參數與模擬所得的時程參數能在數次迭代內收斂一致。

 但因由模擬重組時程參數須花費不少時間,故本論文中將時程參數分解為等候時間、作業時間和傳送時間三部份,再將實際會變動等候時間,利用 產能負荷率與等候時間的關係曲線 (piecewise curve) 求得,然後重組時程參數,提供產能負荷模組使用,並證明在迭代數次後產能負荷模組所使用的時程參數與本論文所得到的時程參數在經過數次的迭代之後會收斂到 一致,並縮短估算時程參數的電腦運算時間。

本論文提出作業員人力規劃與調派模式,目的是要透過作業人員的妥善安排,避免重要機台等待作業員的情形發生,以提高機台使用效率,提升整廠的總產出率。

 動態作業人員人規劃與調派模式,為一動態模式,每隔一段時間區段,依照目前生產線上的狀況,預估下一時間區段未來各工作站的生產需 求,依此做人員安排,在生產需求高的工作站多安排一些作業員,避免其因為等待作業員而造成生產損失。包含四個方法:(1)產能負荷預估方法,利用指數平滑 法預測批量在工作站的等候時間,依此計算作業流程時間後,依照目前生產線的現況以及即將投入的新訂單,預估未來各工作站的生產需求。(2)作業員人力需求 計算方法,依產能負荷預估方法所求得的工作站目標使用效率,利用等候線理論計算各工作站的所需作業員。以上兩個方法可解決長期的人力規劃問題。(3)人力 調整方法,依照使用效率達成率調整各工作站的作業員數,在既有的人力資源條件下,讓整體產出最大。(4)作業員指派方法,利用指派問題的解法,找出作業員 與機台間最佳的配對。以上四個方法可解決短期人力調派問題。

 本研究以模擬對所提模式進行驗證,獲致以下結果:1.動態作業人員調派模式比靜態作業人員調派模式的產出率高,尤其在產品組合變動的 情形改善效果更明顯。2.動態作業人員調派模式在固定批量數設在剛好滿足產能時,比靜態作業人員調派模式的產出率高;但在固定批量數設得很高時,因為工作 站上的等候批量數很多,批量在工作站的等候時間很長,在這樣的情形下,本模式對產能負荷較不能正確的預估,所以改善效果較差。

1997 1996 1995 1994
由於半導體的快速發展,帶動了電子、電機,尤其資訊業的快速發展。也由於製造技術的提升與價格的降低,以半導體製 成的用品已廣汎出現在我們四周, 半導體與我們的關係也愈形密切。半導體製造業 可說是技術與資金密集的產業。 在半導體需求量大與激烈的國際性競爭環境下,半導體製造業於製造管理方面的 分析工作,如生產規劃(Production Planning)、排程(Scheduling)與產能分析Capacity Analysis)等等,將對其能否獲得較高的獲利情形有著重要的影響。上述的問題雖可藉由數學的解析模型(Analytical Model)表達與評估之。但是,由 於半導體製造系統複雜、不確定的本質,將使得解析模型不易表達真實的半導體 製造環境。模擬模型(Simulation Model)由於其具有較高的彈性、變通性與表達 的真實性,模擬工具對於半導體製造環境而言,將是一個實用、可行的分析工具。

 於本計畫中,我們將提出一套可行的物件導向程式設計方法。接著,我們將針對半導體之前段 (Front-End)製程,利用我們所提出的物件導向程式設計方法之 各步驟,對模擬軟體程式庫設計的工作做一概略、整體的介紹。

眾所周知﹐今日半導體製造業是一種高度競爭的產業﹐顧客的服務非常重要﹐因為不被滿足的顧客將會很快的選擇北業間 其他的競爭者﹐如此一來將造成原供給廠商利益及信譽上的重大損失﹔同時﹐機器的故障 ( machinefailure) ﹑再加工( rework) 以及良率均是晶圓製造過程中主要的不確定性因素﹐且因為作業機器設備均非常昂貴﹐以致於廠商均極度追求設備的高使用率﹐導致抵換等候時間的加長﹐從而造就 相當長的生產週期以及產出時間及量的不確定﹐而造成了生產成本的提升。所以不論是在工廠製程或生產成本方面或是在顧客服務方面﹐產品生產週期的長度及變異 將是最重要的測量指標。

 因此﹐本篇論文是以半導體製造之最低層次的現場排程為基本範圍重點在研究即時派工法則 ( Real-Time dispatching)﹐為什麼是Real-Time ﹖當需要派工決策時 ( 即機台閒置 ) 根據最新的在製品和機台狀況下決策的﹔並以縮短產品生產週期為動機﹐配合電腦整合製造系統記錄的資料﹐追蹤工廠現場的在製品分佈情形﹑設備的狀態來預估未 來生產規劃期間內各機台等候線的度量為觀念﹐利用批量等候加工的時間和預測等候線中等待加工批量的等候量度為判斷指標﹐提出兩種生產線的即時派工法則來縮 短產品生產週期為目的。然後根據Hung [19] 中所用的資料和半導體工廠提供的真實資料﹐利用模擬的方式來驗證兩法則的績效﹐並做一結論來討論兩法則的優劣。

眾所周知,今日半導體製造業是一種高度競爭的產業,顧客的服務非常重要,因為不被滿足的顧客將會很快的選擇此業間其他的競爭者,如此一來將造成原供 給廠商利益及信譽上的重大損失;因此,廠商面對各種產品訂單的準時足量交貨問題之解決,有迫切的需要。而在解決準時足量交貨問題上,不可諱言的,在預定的 交貨時間點訂定適當的安全存量是規避種種不確定性因素所造成之交貨延遲或交貨量短缺等情形發生之最好的方法。訂定適當的安全存量即是本篇論文的目的。在本 篇論文裡,我們以半導體前段製程為背景,提出一個屬於安全存量與兩個生產上的不確定因素---生產前置時間或謂之生產週期與產出的良率---之間的關係。 同時提出一個以生產率為變數的線性函數來表示安全存量的演算法。求算安全存量的線性函數演算法將可以被應用在LP的生產計劃模型中。

 本篇論文另外提出一個在某些已知條件下,利用生產週期的機率分配與每個批量之良好晶方產出或每個批量之產出良率的機率分配,求出在任何地方時間點產出的機率分配。

0
TFT-LCD三大主要製程,分別為TFT陣列(TFT array)製程、面板組裝(cell assembly)製程與模組組裝(module assembly)製程。TFT陣列製程與模組組裝製程良率高達90%以上,面板組裝製程難度最高,因為其良率是TFT-LCD製造程序中最低的。假設當 含有不良面板的TFT玻璃基板與良好面板的CF玻璃基板在進行面板組裝之基板組立製程黏合後,會造成不良面板致使成本損失增加。為減少成本損失,本文即針 對此基板組立製程作生產計劃來有效地解決問題。

 為解決在面板組裝製程中基板組立之TFT玻璃基板與CF玻璃基板配對問題,我們建立線性規劃模式將問題模式化,再利用套裝軟體來求解問題。我們研究的重點在於如何減少良好面板與不良面板黏合造成的損失個數以及降低欠貨,總成本最小化是我們的目標。

 在實務上,並沒有特殊的規則去進行玻璃基板的黏合,而是將來到的玻璃基板隨機進行黏合。因此我們以線性規劃模式與實務的隨機方法做比 較,以了解線性規畫模式是否能有效改善實務的隨機方法的損失成本。實驗結果顯示線性規畫模式的總成本均小於隨機方法的總成本,且線性規畫模式TFT玻璃基 板損失的面板個數與CF玻璃基板損失的面板個數也都明顯的少於隨機方法TFT玻璃基板損失的面板個數與CF玻璃基板損失的面板個數,線性規畫模式相較於實 務的隨機方法損失成本改善幅度顯著。