臺灣博碩士論文加值系統

本研究欲探討具有等候時間限制的多產品共用下游機台生產系統的生產控制問題。產品於上游加工站進行加工後，必須在特定時間內進入下游加工站進行加工，此時間限制稱為作業等候時間限制。若下游在製品違反作業等候時間限制，則會產生重工或報廢成本。且此類系統受機台可靠度、新訂單來到等不確定因素影響，若無良好的控制方法將造成產能利用率下降與生產成本增加。而隨著技術演進，許多機台已發展為可多工生產多種產品的樣貌，本研究考量此種機台的特性做生產系統的控制，並期望能對此類機台產生有效運用產能的控制方法。
本研究透過馬可夫決策過程(Markov Decision Process, MDP)加上動態規劃作為求解方法、以最小化總成本的目標進行求解，並由兩產品共用下游機台模型(ACDCW)推廣至可應用於更多產品的生產系統的多產品共用下游機台演算法(MPCWH)。模擬驗證證明兩個控制方法皆能達到改善成本之目的。

This research develops a dynamic scheduling method for multi-product production systems under process queue time (PQT) constraints, wherein waiting time between consecutive processing steps is constrained by predefined upper limits. If the waiting time of a work-in-process (WIP) violates the corresponding PQT constraint, the WIP may be scrapped or have to be reworked due to quality concern. Machine reliability is another concern in the research. Random machine failure in the system may leads to higher risk of scrap and the increase of cycle time. Thus an effective control method with real time machine reliability considerations is important.
First, admission control method of two-product production system is developed using the technique of Markov decision process. The objective is to minimize total expected waiting and scrap costs. In the system having more than two products, a heuristic is developed based on two product model.
Through the 3 types of experiment design, simulation analysis were implemented. The result of simulation indicates that both two-product model and heuristic used in multiple product system could improve total cost effectively.

中文摘要 i
ABSTRACT ii
目錄 iii
圖目錄 vi
表目錄 ix
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機與研究目的 3
1.2.1 研究動機 3
1.2.2 研究目的 3
1.3 研究流程 4
第二章 文獻回顧 5
2.1 共用機台相關文獻 5
2.2 作業等候時間限制問題相關文獻 6
2.3 解決求解複雜度相關文獻 8
第三章 問題描述與研究方法 9
3.1 問題描述 9
3.2 研究問題假設與定義 10
3.3 報廢機率估計 11
3.4 兩產品共用下游機台模型(ACDCW Model) 14
3.5 多產品共用機台演算法 18
3.5.1 求解模型 20
3.5.2 執行過程 23
第四章 數值範例與模擬驗證 25
4.1 數值範例 25
4.1.1 兩產品共用下游機台模型 25
4.1.2 多產品共用機台演算法 30
4.1.3 ACDCW模型與MPCWH演算法之比較 37
4.2 模擬驗證 38
4.3 實驗設計 42
4.3.1 兩產品單機台生產系統實驗設計 42
4.3.2 三產品單機台生產系統實驗設計 45
4.3.3 三產品多機台生產系統實驗設計 49
4.4 實驗結果─兩產品共用下游機台模型(ACDCW) 52
4.4.1 實驗結果摘要 52
4.4.2 敏感度分析 53
4.5 實驗結果─多產品共用機台演算法(Ⅰ) 59
4.5.1 實驗結果摘要 59
4.5.2 敏感度分析 60
4.6 實驗結果─多產品共用下游機台演算法(Ⅱ) 66
4.6.1 實驗結果摘要 66
4.6.2 敏感度分析 67
4.7 實驗結果─多產品共用下游機台演算法(Ⅲ) 72
4.7.1 實驗結果摘要 72
4.7.2 敏感度分析 72
4.8 小結 75
第五章 結論與未來研究方向 89
5.1 結論 89
5.2 未來研究方向 89
參考文獻 90
附錄一 兩產品共用下游機台模型實驗結果 94
附錄二 三產品共用下游機台模型實驗結果(每站單機台) 117
附錄三 三產品共用下游機台模型實驗結果(每站多機台) 138

[1]Akkerman, R., et al. (2007). "Influence of capacity- and time-constrained intermediate storage in two-stage food production systems." International Journal of Production Research 45(13): 2955-2973.

[2]Altman, E. and A. Shwartz (1989). "Optimal Priority Assignment: A Time Sharing Approach." IEEE Transactions on Automatic Control 34(10): 1098-1102.

[3]Baras, J., et al. (1985). "Two Competing Queues with Linear Costs and Geometric Service Requirements: The μ c-Rule Is Often Optimal." Advances in Applied Probability: 186-209.

[4]Baras, J., et al. (1985). "K competing queues with geometric service requirements and linear costs: The μc-rule is always optimal." Systems & control letters 6(3): 173-180.

[5]Bernier, V. and Y. Frein (2004). "Local scheduling problems submitted to global FIFO processing constraints." International Journal of Production Research(8): 1483-1503.

[6]Cho, L., et al. (2014). Production scheduling with queue-time constraints: Alternative formulations. IIE Annual Conference and Expo 2014.

[7]Fisher, R. A. (1936). "Design of experiments." British Medical Journal 1(3923): 554.

[8]Garnett, O., et al. (2002). "Designing a call center with impatient customers." Manufacturing and Service Operations Management 4(3): 208-227.

[9]Gong, H., et al. (2014). "Parallel-batch scheduling and transportation coordination with waiting time constraint." The Scientific World Journal 2014.

[10]Harrison, J. M. (1975). "DYNAMIC SCHEDULING OF A MULTICLASS QUEUE: DISCOUNT OPTIMALITY." Operations Research 23(2): 270-282.

[11]Hauskrecht, M. (2000). "Value-function approximations for partially observable Markov decision processes." Journal of Artificial Intelligence Research 13: 33-94.

[12]Hernández-Lerma, O. and L. F. Hoyos-Reyes (2001). "A multiobjective control approach to priority queues." Mathematical Methods of Operations Research 53(2): 265-277.

[13]Iravani, F. and B. Balciog̃lu (2008). "On priority queues with impatient customers." Queueing Systems 58(4): 239-260.

[14]Kim, J. and A. R. Ward (2013). "Dynamic scheduling of a GI/GI/1+ GI queue with multiple customer classes." Queueing Systems 75(2-4): 339-384.

[15]Lee, Y.-Y., et al. (2005). Reaction chain of process queue time quality control. ISSM 2005, IEEE International Symposium on Semiconductor Manufacturing, 2005., IEEE.

[16]Lin, K. Y. (2003). "Decentralized admission control of a queueing system: A game-theoretic model." Naval Research Logistics 50(7): 702-718.

[17]Mandelbaum, A. and S. Zeltyn (2009). "Staffing many-server queues with impatient customers: Constraint satisfaction in call centers." Operations Research 57(5): 1189-1205.

[18]Ovacik, I. M. and R. Uzsoy (2012). Decomposition methods for complex factory scheduling problems, Springer Science & Business Media.

[19]Pereira, M. V. and L. M. Pinto (1991). "Multi-stage stochastic optimization applied to energy planning." Mathematical programming 52(1-3): 359-375.

[20]Puterman, M. L. (2014). Markov decision processes: discrete stochastic dynamic programming, John Wiley & Sons.

[21]Robinson, J. K. and R. Giglio (1999). Capacity planning for semiconductor wafer fabrication with time constraints between operations. Winter Simulation Conference Proceedings.

[22]Rosberg, Z. and P. Kermani (1992). "Customer Scheduling Under Queueing Constraints." IEEE Transactions on Automatic Control 37(2): 252-257.

[23]Sadeghi, R., et al. (2015). Production control in semiconductor manufacturing with time constraints. 2015 26th Annual SEMI Advanced Semiconductor Manufacturing Conference, ASMC 2015.

[24]Tassiulas, L. and A. Ephremides (1993). "Dynamic Server Allocation to Parallel Queues with Randomly Varying Connectivity." IEEE Transactions on Information Theory 39(2): 466-478.

[25]Tu, Y. M. and C. L. Chen (2011). "Model to determine the capacity of wafer fabrications for batch-serial processes with time constraints." International Journal of Production Research 49(10): 2907-2923.

[26]Wu, C. H., et al. (2010). "Dynamic production control in a serial line with process queue time constraint." International Journal of Production Research 48(13): 3823-3843.

[27]Wu, C. H., et al. (2012). "Dynamic production control in parallel processing systems under process queue time constraints." Computers and Industrial Engineering 63(1): 192-203.

[28]Yechiali, U. (2007). "Queues with system disasters and impatient customers when system is down." Queueing Systems 56(3-4): 195-202.

[29]Zeltyn, S. and A. Mandelbaum (2005). "Call centers with impatient customers: Many-server asymptotics of the M/M/n + G queue." Queueing Systems 51(3-4 SPEC. ISS.): 361-402.

[30]陳文智 (2002). 考量前置時間與顧客等級為導向的等候線系統研究. 工業工程與管理研究所碩士班. 雲林縣, 國立雲林科技大學. 碩士: 114.

[31]黃思孟 (2012). 半導體封裝廠之短期訂單與機台指派問題. 工業工程與工程管理學系. 新竹市, 國立清華大學. 碩士: 122.

[32]潘柏辰 (2014). 具連續作業等候時間限制之平行多機生產系統控制. 工業工程學研究所. 台北市, 國立國立臺灣大學. 碩士: 71.

[33]蔡建基 (2008). 考量等候時間限制之半導體爐管機台派工法則. 工業工程與工程管理學系工程碩士在職專班. 新竹市, 國立清華大學. 碩士: 108.

[34]蔡啟聰 (1996). 晶圓製造廠考慮等候時間限制之派工策略. 工業工程研究所. 新竹市, 國立交通大學. 碩士: 58.

[35]鄭又精 (2010). 作業等候時間限制下批量及多產品生產系統控制. 工業工程學研究所. 台北市, 國立國立臺灣大學. 碩士: 77.