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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:林欣儀
研究生(外文):Hsin-Yi Lin
論文名稱:以分支定界法求取具時間窗口與群組限制之單一機台批次最小化總完工時間之排程問題
論文名稱(外文):A Branch and Bound Algorithm for a Single Machine Batch Scheduling Problem with Time Window and Job Family Constraints to Minimize Total Completion Time
指導教授:沈國基沈國基引用關係
指導教授(外文):Gwo-Ji Sheen
學位類別:碩士
校院名稱:國立中央大學
系所名稱:工業管理研究所
學門:商業及管理學門
學類:其他商業及管理學類
論文出版年:2020
畢業學年度:108
語文別:英文
論文頁數:57
中文關鍵詞:單一機台批次加工群組限制時間窗口總完工時間分枝定界法
外文關鍵詞:Single machineBatch processingJob familyTime windowTotal completion timeBranch and bound algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:28
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本研究考慮單一機台在群組與時間窗口限制下進行批次加工,求取最小總完工時間之排程問題。本研究設定有數個工件要在同個機台上進行批次加工,每個批次能放入的工件有數量上限。因應半導體製程之特性,每個工件有其製程參數,記錄事先設定好的溫度、濕度、時間等加工限制參數,工件依不同的製程參數可被分類成不同群組,只有相同群組的工件才能在同一批次中進行加工。在時間方面,每個工件不一定同時到達加工站,且根據製程參數中時間的限制,工件在到達工作站後一段時間內一定要開始加工,否則該工件會報廢,本研究依此兩時間限制作為工件的時間窗口限制其開始加工時間。
我們提出一分支定界法求取問題之最小總完工時間。首先,我們將工件分組產生數個子問題以縮小問題大小提升演算法求解效率,接著在限制下決定哪些工件可以被放在同批次中進行加工,窮舉所有可能的工件組合後決定其加工順序並且提出刪枝的方法提高演算法求解速度。實驗的分析顯示,我們所提出的分支定界法所求取的解為最佳解,我們也證明事先將工件分組能提升演算法之效率,減少運算時間高達83.87%。另外,我們逐一檢視刪枝方法的表現並根據結果將其順序重新排列,演算法的效率也能有所提升。
Semiconductor manufacturing features several characteristics: recipe, Q-time, batch processing. Recipe records the process parameters such as time, temperature, humidity, chemical restriction, etc. Q-time is the time constraint of jobs. Motivated by these characteristics, we study a single machine batch scheduling problem, where jobs are processed simultaneously. Using the three fields α | β | γ, our problem can be represented as 1 | p-batch,r_j,R_j,┤ incompat | ∑C_j┤. We assume there are n jobs with arbitrary release time and should start to process in remaining lifetime. Jobs has its own recipe and jobs using the different recipe can’t be processed together.
We develop a Branch and bound algorithm to minimize total completion time of our problem. First, we separate jobs into several groups by a grouping method to narrow down the problem size, then we enumerate all the possible combinations of batches and assign one of them after initial scheduling while branching out. We propose several propositions and a bounding scheme to cut off some branches. The computational analysis shows that the solution our Branch and bound algorithm found is optimal and the grouping method can effectively decrease 83.87% of run time. Finally, we find that the sequence of propositions while applying them to eliminate nodes can improve the efficiency of our algorithm.
摘要 i
Abstract ii
Contents iii
List of Figures v
List of Tables vi
Chapter 1 Introduction 1
1.1 Research background and motivation 1
1.2 Problem definition 2
1.3 Research objective 3
1.4 Research methodology 4
1.5 Research framework 4
Chapter 2 Literature Review 6
2.1 Single machine batch processing 6
2.2 Scheduling problems with job family constraint 7
2.3 Scheduling problems with time window constraint 8
2.4 Branch and bound algorithm 9
Chapter 3 Methodology 10
3.1 Notations 10
3.2 Propositions 11
3.3 Branch and bound 20
3.3.1 Node 20
3.3.2 Grouping method 21
3.3.3 Branching scheme 21
3.3.4 Searching strategy 23
3.3.5 Bounding scheme 24
3.3.6 Branch and bound algorithm 27
Chapter 4 Computational Analysis 33
4.1 Generating test problems 33
4.2 Performance of the Branch and bound algorithm 33
4.2.1 Validation of branch and bound algorithm 34
4.2.2 Performance of Grouping method 36
4.3 Performances of propositions and lower bound 39
Chapter 5 Conclusion 43
5.1 Research contribution 43
5.2 Research limitation 44
5.3 Further research 44
Reference 45
Reference
[1] Ahmadi, J. H., Ahmadi, R. H., Dasu, S., & Tang, C. S., Batching and Scheduling Jobs on Batch and Discrete Processors. Operations Research, 40(4), 750–763, 1992.
[2] Azizoglu, M., & Webster, S., Scheduling a batch processing machine with incompatible job families. Computers and Industrial Engineering, 39(3–4), 325–335, 2001.
[3] Balasubramanian, H., Mönch, L., Fowler, J., & Pfund, M., Genetic algorithm based scheduling of parallel batch machines with incompatible job families to minimize total weighted tardiness. International Journal of Production Research, 42(8), 1621–1638, 2004.
[4] Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M. Y., Potts, C. N., Tautenhahn, T., & Van De Velde, S. L., Scheduling a batching machine. Journal of Scheduling, 1(1), 31–54, 1998.
[5] Chand, S., Traub, R., & Uzsoy, R., Single-machine scheduling with dynamic arrivals: Decomposition results and an improved algorithm. Naval Research Logistics, 43(5), 709–719, 1996.
[6] Chandru, V., Lee, C. Y., & Uzsoy, R., Minimizing total completion time on batch processing machines. International Journal of Production Research, 31(9), 2097–2121, 1993.
[7] Chandru, Vijaya, Lee, C. Y., & Uzsoy, R., Minimizing total completion time on a batch processing machine with job families. Operations Research Letters, 13(2), 61–65, 1993.
[8] Cheng, B., Cai, J., Yang, S., & Hu, X., Algorithms for scheduling incompatible job families on single batching machine with limited capacity. Computers and Industrial Engineering, 75(1), 116–120, 2014.
[9] Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R.,Optimization and approximation in deterministic machine scheduling: a survey. Annals of Discrete Mathematics, 5, 287–326, 1979.
[10] Hochbaum, D. S., & Landy, D., Scheduling semiconductor burn-in operations to minimize total flowtime. Operations Research, 45(6), 874–885, 1997.
[11] Kurz, M. E., & Mason, S. J., Minimizing total weighted tardiness on a batch-processing machine with incompatible job families and job ready times. International Journal of Production Research, 46(1), 131–151, 2008.
[12] Land, A. H., & Doig, A. G., The Econometric Society. The Economic Journal, 42(166), 331, 1960.
[13] Li, S., A hybrid two-stage flowshop with part family, batch production, major and minor set-ups. European Journal of Operational Research, 102(1), 142–156, 1997.
[14] Mathirajan, M., & Sivakumar, A. I., A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor. International Journal of Advanced Manufacturing Technology, 29(9–10), 990–1001, 2006.
[15] Morrison, D. R., Jacobson, S. H., Sauppe, J. J., & Sewell, E. C., Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optimization, 19, 79–102, 2016.
[16] Morrison, D. R., Sauppe, J. J., Zhang, W., Jacobson, S. H., & Sewell, E. C., Cyclic Best First Search: Using Contours to Guide Branch-and-Bound Algorithms. Naval Research Logistics (NRL), 64(1), 64–82, 2017.
[17] Mosheiov, G., Due-date assignment with asymmetric earliness-tardiness cost. Journal of the Operational Research Society, 54(11), 1222–1224, 2003.
[18] Potts, C. N., & Kovalyov, M. Y., Scheduling with batching: a review. European Journal of Operational Research, 120(2), 228–249, 2000.
[19] Su, L. H., A hybrid two-stage flowshop with limited waiting time constraints. Computers and Industrial Engineering, 44(3), 409–424, 2003.
[20] Sung, C. S., & Choung, Y. I., Minimizing makespan on a single burn-in oven in semiconductor manufacturing. European Journal of Operational Research, 120(3), 559–574, 2000.
[21] Sung, C. S., Choung, Y. I., Hong, J. M., & Kim, Y. H., Minimizing makespan on a single burn-in oven with job families and dynamic job arrivals. Computers and Operations Research, 29(8), 995–1007, 2002.
[22] Tangudu, S. K., & Kurz, M. E., A branch and bound algorithm to minimise total weighted tardiness on a single batch processing machine with ready times and incompatible job families. Production Planning and Control, 17(7), 728–741, 2006.
[23] Uzsoy, R., Scheduling a single batch processing machine with non-identical job sizes. International Journal of Production Research, 32(7), 1615–1635, 1994.
[24] Uzsoy, R., Scheduling batch processing machines with incompatible job families. International Journal of Production Research, 33(10), 2685–2708, 1995.
[25] Webster, S., & Baker, K. R., Scheduling groups of jobs on a single machine. In Operations Research (Vol. 43, Issue 4, pp. 692–703),1995.
[26] Yan, P., Chu, C., Yang, N., & Che, A., A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows. International Journal of Production Research, 48(21), 6461–6480, 2010.
[27] Yao, S., Jiang, Z., & Li, N., A branch and bound algorithm for minimizing total completion time on a single batch machine with incompatible job families and dynamic arrivals. Computers and Operations Research, 39(5), 939–951, 2012.
電子全文 電子全文(網際網路公開日期:20230731)
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔