具連續作業等候時間限制之平行多機生產系統控制

Production Control in Parallel Multi-tool Systems under Sequential Process Queue Time Constraints

潘柏辰

馬可夫決策過程 ； 動態規劃 ； 作業等候時間限制 ； 啟發式演算法 ； Markov decision process ； Dynamic programming ； Process queue time constraints ； Heuristic

臺灣大學工業工程學研究所學位論文

2014年

碩士

吳政鴻

繁體中文

本研究探討具連續作業等候時間限制下，平行多機生產系統的動態允入控制策略。連續作業等候時間限制為：序列式生產系統中任兩連續製程，產品於上游加工站進行加工後，必須在特定時間內進入下游加工站進行加工，此時間限制稱為作業等候時間限制。若下游在製品違反作業等候時間限制，則會產生重工或報廢成本。且此類系統受機台可靠度、新訂單來到等不確定因素影響，若無良好的控制方法將造成產能利用率下降與生產成本增加。 近代產業常存在作業等候時間限制的問題，例如在半導體產業中，若在製品違反作業等候時間限制，則可能會造成晶圓表面氧化而須重製或報廢。隨著先進製程發展，具作業等候時間限制的製程數急遽增加，另外站點機台數增加也讓派工策略更為困難，因此有必要針對此類型問題，發展妥善的生產管制策略。 本研究基於馬可夫決策過程，以正規化方法將連續時間軸轉換為事件導向的離散時間軸，發展多工作站多機台啟發式控制法(MMHC)。MMHC利用子系統拆解法將多工作站系統拆解為數個兩工作站子系統，針對兩工作站子系統發展動態規劃模型，目標為最小化總生產成本，再將子系統求解結果組合為動態控制策略。最後以系統模擬與其他文獻提出的方法進行比較，結果顯示MMHC控制策略能有效降低總生產成本。

Production control in parallel multi-tool systems under sequential process queue time constraints is studied in this research. When WIP finished an upstream process step, the WIP should be processed at the next process step within a given amount of time. The time constraint is called the process queue time constraint. Any violation of the process queue time constraint seriously impacts yield quality and incurs significant scrap costs. In the semiconductor industry, the violation of process queue time constraint may cause the wafer surface oxidation to be reproduced or scrapped. Under the sequential process queue time constraints and multi-tool production environment, the dispatching strategy is hard to be defined. Besides, machine reliability and demand uncertainties also make the production control difficult, production managers need to balance the need for achieving production targets and yield quality. The Multi-step with Multi-tool Heuristic Control (MMHC) is developed to minimize long-run average production cost. The MMHC strategy is formulated with stochastic dynamic programming. The model objective is to minimize the sum of inventory holding costs and scrap costs. The simulation results reveal that our method significantly reduces total production costs.

1. [1]Akcalt, E., Nemoto, K., & Uzsoy, R. (2001). Cycle-time improvements for photolithography process in semiconductor manufacturing. IEEE Transactions on Semiconductor Manufacturing, 14(1), 48-56.
   連結：
2. [2]Akkerman, R., Van Donk, D. P., & Gaalman, G. (2007). Influence of capacity-and time-constrained intermediate storage in two-stage food production systems. International Journal of Production Research, 45(13), 2955-2973.
   連結：
3. [3]Archibald, T., Black, D., & Glazebrook, K. (2009). An index heuristic for transshipment decisions in multi-location inventory systems based on a pairwise decomposition. European Journal of Operational Research, 192(1), 69-78.
   連結：
4. [4]Ayesta, U., Jacko, P., & Novak, V. (2011). A nearly-optimal index rule for scheduling of users with abandonment. INFOCOM, Proceedings IEEE.
   連結：
5. [5]Bautista, J., & Pereira, J. (2009). A dynamic programming based heuristic for the assembly line balancing problem. European Journal of Operational Research, 194(3), 787-794.
   連結：
6. [6]Bernier, V., & Frein, Y. (2004). Local scheduling problems submitted to global FIFO processing constraints. International Journal of Production Research, 42(8), 1483-1503.
   連結：
7. [8]Chang, K. H., & Chen, W. F. (2003). Admission control policies for two-stage tandem queues with no waiting spaces. Computers & Operations Research, 30(4), 589-601.
   連結：
8. [9]Chen, C. L., & Tang, T. I. (2012). Flexible flow line scheduling problems with re-entrant flows and queue-time constraints. IEEE Automatic Control and Artificial Intelligence (ACAI 2012), International Conference on, 1065-1068.
   連結：
9. [10]Chou, Y. C., & Wu, C. S. (2002). Economic analysis and optimization of tool portfolio in semiconductor manufacturing. IEEE Transactions on Semiconductor Manufacturing, 15(4), 447-453.
   連結：
10. [11]Cil, E. B., Ormeci, E. L., & Karaesmen, F. (2009). Effects of system parameters on the optimal policy structure in a class of queueing control problems. Queueing Systems, 61(4), 273-304.
    連結：
11. [12]Down, D. G., Koole, G., & Lewis, M. E. (2011). Dynamic control of a single-server system with abandonments. Queueing Systems, 1-28.
    連結：
12. [13]Economou, A., & Kanta, S. (2008). Optimal balking strategies and pricing for the single server Markovian queue with compartmented waiting space. Queueing Systems, 59(3), 237-269.
    連結：
13. [14]Harjunkoski, I., & Grossmann, I. E. (2001). A decomposition approach for the scheduling of a steel plant production. Computers & Chemical Engineering, 25(11-12), 1647-1660.
    連結：
14. [15]Hauskrecht, M. (2000). Value-function approximations for partially observable Markov decision processes. Journal of Artificial Intelligence Research, 13, 33-94.
    連結：
15. [16]Kim, C., & Dudin, S. (2011). Priority tandem queueing model with admission control. Computers & Industrial Engineering, 61(1), 131-140.
    連結：
16. [17]Kitamura, S., Mori, K., & Ono, A. (2006). Capacity planning method for semiconductor fab with time constraints between operations. SICE-ICASE, International Joint Conference.
    連結：
17. [18]Kocaga, Y. L., & Ward, A. R. (2010). Admission control for a multi-server queue with abandonment. Queueing Systems, 65(3), 275-323.
    連結：
18. [19]Koole, G. (2006). Monotonicity in Markov reward and decision chains: Theory and applications. Foundations and Trends in Stochastic Systems, 1(1), 1-76.
    連結：
19. [20]Ku, C. Y., & Jordan, S. (1997). Access control to two multi-server loss queues in series. IEEE Transactions on Automatic Control, 42(7), 1017-1023.
    連結：
20. [22]Lee, Y. Y., Chen, C., & Wu, C. (2005). Reaction chain of process queue time quality control. Semiconductor Manufacturing, IEEE International Symposium on, 47-50.
    連結：
21. [23]Ma, Z., Caines, P. E., & Malhame, R. P. (2010). Control of Admission and Routing in Loss Networks: Hybrid Dynamic Programming Equations. IEEE Transactions on Automatic Control, 55(2), 350-366.
    連結：
22. [24]Mao, J. F., & Christos, G. C. (2009). Optimal control of multi-stage discrete event systems with real-time constraints. IEEE transactions on Automatic Control, 54(1), 108-123.
    連結：
23. [25]Meyn, S. P. (2005). Workload models for stochastic networks: Value functions and performance evaluation. IEEE Transactions on Automatic Control, 50(8), 1106-1122.
    連結：
24. [26]Perel, N., & Yechiali, U. (2010). Queues with slow servers and impatient customers. European Journal of Operational Research, 201(1), 247-258.
    連結：
25. [27]Puterman, M. L. (1994). Markov decision processes: discrete stochastic dynamic programming, John Wiley & Sons, Inc.
    連結：
26. [29]Robinson, J. K., & Giglio, R. (1999). Capacity planning for semiconductor wafer fabrication with time constraints between operations. Simulation Conference Proceedings, 1, 880-887.
    連結：
27. [30]Rose, O. (1999). CONLOAD-a new lot release rule for semiconductor wafer fabs. Simulation Conference Proceedings, 1, 850-855.
    連結：
28. [31]Scholl, W., & Domaschke, J. (2000). Implementation of modeling and simulation in semiconductor wafer fabrication with time constraints between wet etch and furnace operations. IEEE Transactions on Semiconductor Manufacturing, 13(3), 273-277.
    連結：
29. [32]Vindevogel, J., & Sandra, P. (1991). Resolution optimization in micellar electrokinetic chromatography: use of Plackett-Burman statistical design for the analysis of testosterone esters. Analytical Chemistry, 63(15), 1530-1536.
    連結：
30. [34]Wang, K. H., & Chang, Y. C. (2002). Cost analysis of a finite M/M/R queueing system with balking, reneging, and server breakdowns. Mathematical methods of operations research, 56(2), 169-180.
    連結：
31. [35]Wein, L. M. (1988). Scheduling semiconductor wafer fabrication. IEEE Transactions on Semiconductor Manufacturing, 1(3), 115-130.
    連結：
32. [36]Wu, C. H., Down, D. G., & Lewis, M. E. (2008). Heuristics for allocation of reconfigurable resources in a serial line with reliability considerations. IIE Transactions, 40(6), 595-611.
    連結：
33. [37]Wu, C. H., Lewis, M. E., & Veatch, M. (2006). Dynamic allocation of reconfigurable resources in a two-stage Tandem queueing system with reliability considerations. IEEE Transactions on Automatic Control, 51(2), 309-314.
    連結：
34. [38]Wu, C. H., Lin, J. T., & Chien, W. C. (2010). Dynamic production control in a serial line with process queue time constraint. International Journal of Production Research, 48(13), 3823-3843.
    連結：
35. [39]Wu, C. H., Lin, J. T., & Chien, W. C. (2012). Dynamic production control in parallel processing systems under process queue time constraints. Computers & Industrial Engineering, 63(1), 192-203.
    連結：
36. [40]Xu, S. H., Gao, L., & Ou, J. (2007). Service performance analysis and improvement for a ticket queue with balking customers. Management Science, 53(6), 971-990.
    連結：
37. [41]Yang, D. L., & Chern, M. S. (1995). A two-machine flowshop sequencing problem with limited waiting time constraints. Computers & Industrial Engineering, 28(1), 63-70.
    連結：
38. [42]Yechiali, U. (2007). Queues with system disasters and impatient customers when system is down. Queueing Systems, 56(3), 195-202.
    連結：
39. [43]Zhang, B., & Ayhan, H. (2013). Optimal admission control for tandem queues with loss. IEEE Transactions on Automatic Control, 58(1), 163-167..
    連結：
40. [44]巫啟彰 (2006). 半導體晶圓製造廠中等候時間限制作業的放行控制方法. 碩士論文, 國立清華大學.
    連結：
41. [47]張恆維 (2009). 產能配置與設備維修之動態整合研究. 碩士論文, 國立台灣大學.
    連結：
42. [49]曾俊翔 (2012). 連續作業等候時間限制下之多工作站生產系統控制. 碩士論文, 國立臺灣大學.
    連結：
43. [50]黃嘉常 (2007). 考量等候時間限制之半導體製造在製品分配及控制方法. 碩士論文, 國立清華大學.
    連結：
44. [53]鄭又精 (2010).作業等候時間限制下批量及多產品生產系統控制. 碩士論文, 國立臺灣大學.
    連結：
45. [7]Bonvik, A. M., Couch, C., & Gershwin, S. B. (1997). A comparison of production-line control mechanisms. International Journal of Production Research, 35(3), 789-804.
46. [21]Law, A. M., & Kelton, W. D. (1991). Simulation modeling and analysis, McGraw-Hill New York.
47. [28]Qi, C., Sivakumar, A. I., & Gershwin, S. B. (2009). An efficient new job release control methodology. International Journal of Production Research, 47(3), 703-731.
48. [33]Wang,K., Li, N., & Jiang, Z. (2010). Queueing system with impatient customers: A review. Service Operations and Logistics and Informatics(SOLI), IEEE International Conference on, 82-87.
49. [45]林則孟 (2001). 系統模擬理論與應用. 滄海書局.
50. [46]涂漢威 (2005). 晶圓製造廠考慮等候時間限制之批量放行法則. 碩士論文, 國立清華大學.
51. [48]許淑芬 (1998). 具等候時間窗口限制之零工式生產排程問題. 碩士論文, 國立中央大學.
52. [51]廖紳凱 (2004). 考量等候時間限制之半導體生產排程問題. 碩士論文, 國立清華大學.
53. [52]蔡啟聰 (1995). 晶圓製造廠考慮等候時間限制之派工策略. 碩士論文, 國立交通大學.

1. 姚怡均(2017)。考量機台損耗之非等效動態生產系統派工與保養。臺灣大學工業工程學研究所學位論文。2017。1-106。 
2. 陳渝婷(2016)。具等候時間限制之下游多產品機台生產系統控制。臺灣大學工業工程學研究所學位論文。2016。1-160。