![]() |
|
以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數:95 、訪客IP:18.190.176.131
姓名 葉致宏(Zhi-Hong Ye) 查詢紙本館藏 畢業系所 工業管理研究所 論文名稱 以分支定界法求取具有就緒時間與工件族限制之單一機台批次處理問題之最小化總完工時間
(A branch and bound algorithm to minimize total completion time on single batch processing machine with release time and job families constraints)相關論文 檔案 [Endnote RIS 格式]
[Bibtex 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
至系統瀏覽論文 (2026-1-1以後開放)
摘要(中) 在本研究中,我們考慮單一機台批次處理在就緒時間、不同作業大小和不兼容的作業族之排程問題。目標是使用分支定界演算法求取最小化的總完工時間。本項研究中,多個工件被設置為在同台機器上進行批次加工。因應半導體製造以下幾個特徵 : 批處理,配方,作業到達時間。批處理表示同時加工多個作業。配方記錄每一個作業的過程參數,例如時間,溫度,濕度,化學限制等。具有相同配方的作業具有同樣的加工時間,並且可以在同個批次中同時進行加工。在作業抵達的時間方面,每一個工件抵達加工站的時間不一定相同。本研究依據這些特性發展分支定界演算法來求取最小總完工時間之問題。
我們將工件依據使用的配方進行分組以縮小問題範圍,並製定搜尋策略來決定如何探索節點。一個好的搜尋策略可以改善搜尋的效率以更快地找到最優解。除此之外,我們提出了一些命題,這些命題也可以用來提高算法的效率。我們發展的分支定界演算法,將在隨機產生的問題實例上進行測試。摘要(英) In our research, we think out the scheduling problem about a single batch processing machine with release time, incompatible job families and different job sizes;our main purpose is to minimize total completion time. In our research, we suppose a set of n jobs to be processed in batches on single machine. In response to the following characteristics of semiconductor manufacturing: batch processing machine, size of jobs, recipe, job arrival time. As long as the total size of the jobs in the batch does not exceed the maximum batch capacity, the batch machine can process multiple jobs simultaneously. The recipe records the process parameters of each job. Only jobs of the same recipe can be put into the same batch to process and jobs from same recipe with same processing time. In terms of job arrival time, each job does not necessarily arrive at the processing station at the same time. Based on these characteristics, this research develops a branch and bound algorithm to find the minimal total completion time of the problem.
We develop the batching method to narrow the scope of the problem and develop the searching strategy to decide how to explore nodes. A good searching strategy can help us find the optimal solution quicker and may increase the algorithm efficiency. Furthermore, we purpose several propositions that are also use to improve the efficiency of algorithm. Finally, in the computational experiment, we will test the branch and bound algorithm we proposed on randomly generated problem instances.關鍵字(中) ★ 單一機台
★ 批次加工
★ 作業族
★ 總完工時間
★ 分支定界演算法關鍵字(英) ★ Single machine
★ Batch processing
★ Job families
★ Total completion time
★ Branch and bound algorithm論文目次 摘要 i
Abstract ii
Content 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 3
1.5 Research framework 3
Chapter 2 Literature review 5
2.1 Problem of single batch processing machine 5
2.2 Problem of job family and release time constraints 6
2.3 Problem of branch and bound algorithm 7
Chapter 3 Methodology 8
3.1 Notations 8
3.2 Properties and Propositions 9
3.3 Branch and bound algorithm 15
3.3.1. Node representation 15
3.3.2. Batching method 15
3.3.3. Branching scheme 16
3.3.4. Searching strategy 17
3.3.5. Bounding scheme 19
3.3.6. Branch and bound algorithm 21
Chapter 4 Computational Analysis 24
4.1 Generate test problems 24
4.2 Validation of our branch and bound algorithm 25
4.3 Evaluation of our branch and bound algorithm 26
4.3.1 Performance of our branch and bound algorithm 27
4.3.2 Performance of Propositions and Lower bound 28
Chapter 5 Conclusion 32
5.1 Research contribution 32
5.2 Impact of research restrictions 33
5.3 Further research 33
Appendix 34
Reference 36參考文獻 [1] Azizoglu, M., & Webster, S., Scheduling a batch processing machine with incompatible job families. Computers and Industrial Engineering, 39(3–4), 325–335, 2001.
[2] Azizoglu, M. & Webster, S., Scheduling a batch processing machine with non-identical job sizes. International Journal of Production Research, 38, 2173–2184, 2000.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] Dupont, L. & Dhaenens-Flipo, C., Minimising the makespan on a batch machine with non-identical job sizes: an exact procedure. Computer Operation Research, 29, 807–819, 2002.
[9] Hochbaum, D. S., & Landy, D., Scheduling semiconductor burn-in operations to minimize total flowtime. Operations Research, 45(6), 874–885, 1997.
[10] 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.
[11] 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.
[12] 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.
[13] Potts, C. N., & Kovalyov, M. Y., Scheduling with batching: a review. European Journal of Operational Research, 120(2), 228–249, 2000.
[14] 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.
[15] 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.
[16] 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.
[17] Uzsoy, R., Scheduling a single batch processing machine with non-identical job sizes. International Journal of Production Research, 32(7), 1615–1635, 1994.
[18] Uzsoy, R., Scheduling batch processing machines with incompatible job families. International Journal of Production Research, 33(10), 2685–2708, 1995.
[19] Webster, S., & Baker, K. R., Scheduling groups of jobs on a single machine. In Operations Research (Vol. 43, Issue 4, pp. 692–703),1995.指導教授 沈國基(Gwo-Ji Sheen) 審核日期 2021-7-14 推文 plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
網路書籤 Google bookmarks
del.icio.us
hemidemi
myshare