(3.235.108.188) 您好!臺灣時間:2021/02/27 03:04
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:李品寬
研究生(外文):Pin-Kuan Lee
論文名稱:以組合式班德切面求解多站作業等候時間限制之排程問題
論文名稱(外文):Flow shop production scheduling problem withqueue time constraints using combinatorial Benders’ cuts
指導教授:洪一薰洪一薰引用關係
指導教授(外文):I-Hsuan Hong
口試日期:2017-07-21
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:工業工程學研究所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2017
畢業學年度:105
語文別:中文
論文頁數:36
中文關鍵詞:生產排程流程式生產等候時間限制班德氏分解法
外文關鍵詞:schedulingflow shopqueue time constraintcombinatorial Benders’ cut.
相關次數:
  • 被引用被引用:0
  • 點閱點閱:106
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在實務的產線上,許多產品具有作業等候時間限制的特性(queue time constraint),如半導體製造以及食品製造。混整數規劃(Mixed-Integer Linear Programming; MILP)常被使用於這類問題的求解,然而此類型的問題求解時間會隨著產品數量增加而成指數成長。本研究先利用大M法(big M method)建立一套具有等候時間限制的問題模型,並使用優先值設定(priority-order setting) 針對產品先進先出(FIFO, first in first out)特性進行簡化,同時也使模型對於產品先後順序的處理更具有彈性;接著利用組合式班德切面(CBC, combinatorial Benders’ cut) 將混整數模型拆解成兩個獨立的模型,分別為整數模型(integer part)以及連續型模型(continuously part),並分開求解,CBC法亦可結合模型中指派問題的特性,搭配程式條件語法(if-then rule)後就能對多數大M限制式進行鬆弛,大幅減少限制式的數量,縮短求解時間。本研究亦發現在特定製程時間設定的即時控制系統上,混整數規劃模型可以利用階段性求解(phase-step solved)來達到與全域求解一樣的效果,階段性求解會使得決策變數大幅縮減,大幅減少找求解時間。最後模擬結果顯示,在本研究的即時控制系統中,結合上述方法可以較單純MILP短時間內得到更好的解,也確實能夠求解較大的問題,而長時間模擬的結果我們也比較了其他演算法,例如先進先出法(FIFO)、門檻值設定法(threshold)以及反應鏈法(reaction chains),結果顯示CBC可以有更多的產出與較少的損壞。
The queue time constraint is a common restriction in many production processes such as semiconductor production and food industry. The mixed-integer linear programming (MILP) is a common practice for the scheduling problem with queue time constraints. However, the complexity of MILP-based models increases enormously as the number of jobs increases. In our research, we formulate a model with queue time constraint by the big-M method. The first-in-first-out (FIFO) rule can be implemented by the priority-order setting in the proposed model. We solve the MILP with combinatorial Benders’ cut (CBC), where the MILP model is decomposed into two independent parts: integer and continuously parts. The decomposition technique allows us to speed up the computational time and combines the if-then rule to reduce redundant constraints with the big-M method. We also prove that the phase-step achieves the optimal solution and effectively reduces the computational time by only considering a short planning horizon. Finally, the simulation results demonstrate that the proposed method outperforms the MILP based mothed. In the long run, our mothed also outperforms other approaches such as FIFO, threshold, and reaction chains in terms of the number of scrap jobs and throughputs.
誌謝 i
摘要 ii
Abstract iii
目錄 iv
圖目錄 vi
表目錄 vii
第一章 緒論 1
第二章 數學模型 4
2.1. 即時控制系統(Real-time control system)與等候時間限制 4
2.2. 大M法相較於時間序列法建模之優缺點 5
2.3. 參數與變數 7
2.4. 模型 8
2.4.1. 目標式 8
2.4.2. 限制式 9
2.5. 優先值排序設定(Priority-order setting) 11
第三章 求解方法 14
3.1. 組合式班德切面(Combinatorial Benders’ cut) 15
3.2. 階段性工作站求解(Phase-step solved) 18
第四章 數值分析與比較 21
4.1. 求解能力表現 21
4.2.1. 模擬環境設定 24
4.2.2. 結果比較 25
第五章 結論與未來方向 29
參考文獻 30
附錄 33
階段性工作站證明 33
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.
Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238-252.
Bernier, V., & Frein, Y. (2004). Local scheduling problems submitted to global FIFO processing constraints. International Journal of Production Research, 42(8), 1483-1503.
Canto, S. P. (2008). Application of Benders’ decomposition to power plant preventive maintenance scheduling. European Journal of Operational Research, 184(2), 759-777.
Codato, G., & Fischetti, M. (2006). Combinatorial Benders'' cuts for mixed-integer linear programming. Operations Research, 54(4), 756-766.
Geoffrion, A. M. (1972). Generalized benders decomposition. Journal of Optimization Theory and Applications, 10(4), 237-260.
Guo, C., Zhibin, J., Zhang, H., & Li, N. (2012). Decomposition-based classified ant colony optimization algorithm for scheduling semiconductor wafer fabrication system. Computers & Industrial Engineering, 62(1), 141-151.
IBM ILOG (2014). CPLEX Optimizer, version 12.6.
Kaufman, L., & Broeckx, F. (1978). An algorithm for the quadratic assignment problem using Bender''s decomposition. European Journal of Operational Research, 2(3), 207-211.
Kim, Y. D., Joo, B. J., & Choi, S. Y. (2010). Scheduling wafer lots on diffusion machines in a semiconductor wafer fabrication facility. IEEE Transactions on Semiconductor Manufacturing, 23(2), 246-254.
Lee, Y. Y., Chen, C. T., & Wu, C. (2005). Reaction chain of process queue time quality control. Semiconductor Manufacturing, 2005. ISSM 2005, IEEE International Symposium on, 47-50. IEEE.
Microsoft Corporation: C# Language Specification Version 5.0. (2015).
Nawaz, M., Enscore, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91-95.
Rose, O. (1999). CONLOAD—a new lot release rule for semiconductor wafer fabs. Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future-Volume 1, 850-855. ACM.
So, A., & Liang, B. (2009). Optimal placement and channel assignment of relay stations in heterogeneous wireless mesh networks by modified bender’s decomposition. Ad Hoc Networks, 7(1), 118-135.
Tarvin, D. A., Wood, R. K., & Newman, A. M. (2016). Benders decomposition: Solving binary master problems by enumeration. Operations Research Letters, 44(1), 80-85.
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.
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.
Wu, C. H., Chien, W. C., Chuang, Y. T., Cheng, Y. C. (2016). Multiple product admission control in semiconductor manufacturing systems with process queue time (PQT) constraints. Computers & Industrial Engineering.
Wu, K., Zhao. N., Gao, L., & Lee, C. K. M. (2016). Production control policy for tandem workstations with constant service times and queue time constraints. International Journal of Production Research, 54(21), 6302-6316.
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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔