(3.236.118.225) 您好!臺灣時間:2021/05/17 09:22
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:李穎琪
研究生(外文):Ying-Chi Lee
論文名稱:節省法為基礎之分支定界法以決定機器合適度區間之零工式批量排程問題
論文名稱(外文):A Saving Method-based Branch-and-Bound Algorithm for Machine Eligibility Period Determination Problem on Job Shop Batch Processing
指導教授:沈國基沈國基引用關係
指導教授(外文):Gwo-Ji Sheen
學位類別:碩士
校院名稱:國立中央大學
系所名稱:工業管理研究所
學門:商業及管理學門
學類:其他商業及管理學類
論文出版年:2020
畢業學年度:108
語文別:英文
論文頁數:61
中文關鍵詞:零工式生產存活時間限制批量分支定界排程最晚完工時間
外文關鍵詞:Job ShopRemaining life timeBatchBranch and BoundSchedulingMaterial
相關次數:
  • 被引用被引用: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 iii
List of Figures v
List of Tables vi
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Problem Description 2
1.2.1 Batch 2
1.2.2 Material Restrictions 3
1.3 Research Objectives 4
1.4 Research Methodology 4
1.5 Research Framework 5
Chapter 2 Literature Review 6
2.1 Job-Shop Scheduling 6
2.2 Disjunctive Graph 7
2.3 Batch 8
2.4 Time Lags 10
Chapter 3 Branch-and-Bound 12
3.1 Notations 13
3.2 Disjunctive Graph 15
3.3 Proposition 18
3.3.1 Lower Bound 19
3.3.2 Batch 20
3.3.3 The Characteristic of Machine 23
3.3.4 Computing E and S 25
3.3.5 Input and Output Determination 27
3.3.6 Material Consumption 29
3.4 Branch Scheme 29
3.5 Branch and Bound Algorithm 33
3.5.1 Branch and Bound 33
3.5.2 Find the Set of Batches 35
3.5.3 Fixing an Input Batch to Yield a Lower Bound 36
3.5.4 Fixing an Output Batch to Yield a Lower Bound 37
3.5.5 Establishing for Makespan 38
3.5.6 Create a Child Node β 39
Chapter 4 Computational Analysis 41
4.1 Test Problem Generation 41
4.2 Validation of the Branch and Bound Algorithm 42
4.3 Test Problem Efficient 44
Chapter 5 Conclusion 47
5.1 Research Contribution 47
5.2 Research Limitation 47
5.3 Future Research 48
Reference 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)
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top