(3.236.118.225) 您好！臺灣時間：2021/05/17 09:22

### 詳目顯示:::

:

• 被引用:0
• 點閱:42
• 評分:
• 下載:0
• 書目收藏:0
 本文主要探討節省法為基礎之分支定界法以決定機器合適度區間之零工式批量排程問題。此論文將環境以三種相關的單位作探討，由單位小到大分別為Operation、Batch、Period。Operation為每個工件在指定機台的操作。將Operation依工件大小總和、工件族等特性依特定規則組合並同時送進機台加工稱為Batch。Period為機台此次添加物料至下一次添加物料的時間段，Period會根據物料消耗的多寡決定服務多少Batch。我們提出一個分支定界演算法去尋找這個問題的佳解。將利用Proposition以job size及release time計算各種Operation組合的節省面積。每個節點都會計算input operation及output operation的節省面積後得到多個batch，並在input batches及output batches中各選出一個指派到加工順序中成為一個節點，將所有指派可能舉出後便完成分支。本論文依照環境設計出分離圖，分離圖上的分離弧線會依照節點的排程狀況更動，當找到起源點至終節點的最長路徑可得此節點的lower bound。得到可行解之節點的最長路徑並同Upper bound比較，可得目前已知最佳解。最後，我們驗證節省法對物料消耗及尋找批量組合有不錯的表現。並發現節省法可降低批量的列舉數，分離圖計算出最長路徑後也明顯的提高砍支的數目。因此證明此演算法可快速及有效地找到此環境中表現優異的可行解。
 This thesis is mainly designed with a saving method-based branch-and-bound algorithm for machine eligibility period determination problem on job shop batch processing. We discuss the environment in terms of Operation, Batch and Period. Operation is the processing of each job on the designated machine. Combining Operations according to the characteristics of sum of job size, family, etc., combined with specific rules and processed by the machine at the same time is called Batch. Period is the time interval from when the machine starts adding materials to the next time when materials are added. The amount of materials consumed determines how many batches are served by one period.We propose a branch and bound algorithm to find an excellent solution. Proposition will be used to calculate the area savings of multiple operation combinations with job size and release time. Each node will calculate the saving area of input operations and output operations to get batch. Select one of the input batches and output batches and assign them to the processing sequence to become a node. After all possible assignments are listed, the branch is completed.This thesis designs a disjunctive graph according to the problem, and the disjunctive arc on the disjunctive graph will change according to the scheduling status of the node. The longest path from the start point to the end point can get the lower bound of this node. Comparing the longest path of the feasible solution with the upper bound, we can see that the final solution has been obtained.Finally, we verify that the saving method has a good performance on material consumption and finding batch combinations. It is found that the saving method can reduce the enumeration number of the batch. The longest path of the disjunctive graph also significantly increases the number of cut branches. Therefore, it is proved that this algorithm can quickly and effectively find feasible solutions with excellent performance in this environment.
 Contents iiiList of Figures vList of Tables viChapter 1 Introduction 11.1 Background and Motivation 11.2 Problem Description 21.2.1 Batch 21.2.2 Material Restrictions 31.3 Research Objectives 41.4 Research Methodology 41.5 Research Framework 5Chapter 2 Literature Review 62.1 Job-Shop Scheduling 62.2 Disjunctive Graph 72.3 Batch 82.4 Time Lags 10Chapter 3 Branch-and-Bound 123.1 Notations 133.2 Disjunctive Graph 153.3 Proposition 183.3.1 Lower Bound 193.3.2 Batch 203.3.3 The Characteristic of Machine 233.3.4 Computing E and S 253.3.5 Input and Output Determination 273.3.6 Material Consumption 293.4 Branch Scheme 293.5 Branch and Bound Algorithm 333.5.1 Branch and Bound 333.5.2 Find the Set of Batches 353.5.3 Fixing an Input Batch to Yield a Lower Bound 363.5.4 Fixing an Output Batch to Yield a Lower Bound 373.5.5 Establishing for Makespan 383.5.6 Create a Child Node β 39Chapter 4 Computational Analysis 414.1 Test Problem Generation 414.2 Validation of the Branch and Bound Algorithm 424.3 Test Problem Efficient 44Chapter 5 Conclusion 475.1 Research Contribution 475.2 Research Limitation 475.3 Future Research 48Reference 49
 [1] Azizoglu, M., Webster, S. (2001). Scheduling a batch processing machine with incompatible job families. Computers & Industrial Engineering, 39(3-4), 325–335.[2] Brucker, P., Jurisch, B., Sievers, B. (1994). A branch and bound algorithm for the job-shop scheduling problem. Discrete Applied Mathematics, 49(1-3), 107–127.[3] Carlier, J., Pinson, E. (1989). An Algorithm for Solving the Job-Shop Problem. Management Science, 35(2), 164–176.[4] Carlier, J., Pinson, E. (1994). Adjustment of heads and tails for the job-shop problem. European Journal of Operational Research, 78(2), 146–161.[5] Carlier, J., Rebaï, I. (1996). Two branch and bound algorithms for the permutation flow shop problem. European Journal of Operational Research, 90(2), 238–251.[6] Centeno, G., Armacost, R. L. (1997). Parallel machine scheduling with release time and machine eligibility restrictions. Computers & Industrial Engineering, 33(1-2), 273–276.[7] Chandru, V., Lee C.Y., Uzsoy, R. (1993) Minimizing total completion time on batch processing machines, International Journal of Production Research, 31(9), 2097-2121[8] Chen, H., B. Du., George Q,. Huang. 2011. “Scheduling a Batch Processing Machine with Non-Identical Job Sizes: A Clustering Perspective.” International Journal of Production Research 49 (19): 5755–5778.[9] Dupont, L., Dhaenens-Flipo, C. (2002). Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure. Computers & Operations Research, 29(7), 807–819.[10] El Adl, M.K., Rodriguez, A.A., Tsakalis, K.S. (1996). Hierarchical modeling and control of re-entrant semiconductor manufacturing facilities. Proceedings of the 35th Conference on Decision and Control, Kobe, Japan.[11] Fowler, J.W., Hogg, G.L., Phillips, D.T. (1992) Control of multiproduct bulk service diffusion/oxidation processes. liE Transactions,24, 8~96.[12] Garey, M.R., Johnson, D.S. (1979). Computers and intractability: a guide to the theory of NP-completeness. New York: Freeman[13] Jamrus, T., Chien, C.F., Gen, M., Sethanan K. (2018). Hybrid Particle Swarm Optimization Combined with Genetic Operators for Flexible Job-Shop Scheduling Under Uncertain Processing Time for Semiconductor Manufacturing. IEEE Transactions on Semiconductor Manufacturing, 31(1), 32–41.[14] Karimi, N., Davoudpour, H. (2015). A branch and bound method for solving multi-factory supply chain scheduling with batch delivery. Expert Systems with Applications, 42(1), 238–245.[15] Li, X., Li, Y., Wang, Y. (2016). Minimizing makespan on a batch processing machine using heuristics improved by an enumeration scheme. International Journal of Production Research, 55(1), 176–186.[16] Li, X.L., Li, Y.P., Wang, Y. (2017). Minimising makespan on a batch processing machine using heuristics improved by an enumeration scheme, International Journal of Production Research, 55:1, 176-186.[17] Mason, S.J., Fowler, J.W., Carlyle, W.M., Montgomery, D.C. (2005). Heuristics for minimizing total weighted tardiness in complex job shops, International Journal of Production Research, 43:10, 1943-1963.[18] Mazdeh, M. M., Sarhadi, M., Hindi, K. S. (2007). A branch-and-bound algorithm for single-machine scheduling with batch delivery minimizing flow times and delivery costs. European Journal of Operational Research, 183(1), 7486.[19] Mönch, L., Fowler, J. W., Dauzère-Pérès S., Mason, S. J., Rose, O. (2011). A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations. Journal of Scheduling, 14(6), 583–599.[20] Rossi, A., Dini, G. (2007). Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimization method. Robotics and Computer-Integrated Manufacturing, 23(5), 503–516.[21] Sangsawang, C., Sethanan, K., Fujimoto, T., Gen, M. (2015). Metaheuristics optimization approaches for two-stage reentrant flexible flow shop with blocking constraint. Expert Systems with Applications, 42(5), 2395–2410.[22] 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.[23] Sforza, A., Sterle, C. (Eds.). (2017). Optimization and Decision Science: Methodologies and Applications. Springer Proceedings in Mathematics & Statistics.[24] Sheen, G.J., Liao, L.W. (2007). A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags. European Journal of Operational Research, 181(1), 102–116.[25] Tangudu, S. K., Kurz, M. E. (2006). A branch and bound algorithm to minimize total weighted tardiness on a single batch processing machine with ready times and incompatible job families. Production Planning & Control, 17(7), 728–741.[26] Thitipong J., Chen F. C., Mitsuo G., Kanchana S. (2018). Hybrid Particle Swarm Optimization Combined with Genetic Operators for Flexible Job-Shop Scheduling Under Uncertain Processing Time for Semiconductor Manufacturing. IEEE transactions on semiconductor manufacturing, vol. 31, no. 1, 32-41.[27] Uzsoy, R. (1995). Scheduling batch processing machines with incompatible job families. International Journal of Production Research, 33(10), 2685–2708.[28] Uzsoy, R., Lee, CY. and Martin-Vega, L.A. (1992) A review of production planning and scheduling models in the semiconductor industry, part I: system characteristics, performance evaluation and production planning. liE Transactions, 24, 47-60.[29] Wang, H.K., Chien, C.F., Gen, M. (2015). An Algorithm of Multi-Subpopulation Parameters with Hybrid Estimation of Distribution for Semiconductor Scheduling With Constrained Waiting Time. IEEE Transactions on Semiconductor Manufacturing, 28(3), 353–366.[30] Xiao H. (2000). Introduction to semiconductor manufacturing technology. New Jersey: Prentice Hall.
 電子全文(網際網路公開日期：20230731)
 國圖紙本論文
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 動態零工型工廠派工法則模擬研究 2 開放工廠總加權延遲最小化排程問題之研究 3 允許中斷之開放工廠總完工時間最小化問題之研究 4 運用遺傳演算法求解具多部相同類型生產機台之經濟批量排程問題 5 模擬退火法在彈性製造系統排程之應用 6 實際零工式生產派工法則之選擇：靜態系統 7 應用高效率禁區搜尋演算法於有嚴重瓶頸處理機器的派工問題 8 損耗性經濟批量排程問題之研究 9 不可中斷開放工廠總完工時間最小化之排程問題 10 針對半導體廠之酸槽爐管製程發展整合性派工法則以期望降低產品週期時間 11 具裝配作業之零工式工廠排程研究 12 多目標重疊式之零工式排程研究─計步蟻群演算法 13 半導體製造系統之多目標排程 14 以基因演算法求解不可延遲批次排程問題之研究 15 具機器可用時間與機器合適度限制之平行機台排程問題

 無相關期刊

 無相關點閱論文

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室