以分支定界法求取具有就緒時間與工件族限制之單一機台批次處理問題之最小化總完工時間

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：178

、訪客IP：3.144.202.167

姓名

葉致宏(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)

相關論文

★ 以類神經網路探討晶圓測試良率預測與重測指標值之建立	★ 六標準突破性策略—企業管理議題
★ 限制驅導式在製罐產業生產管理之應用研究	★ 應用倒傳遞類神經網路於TFT-LCD G4.5代Cell廠不良問題與解決方法之研究
★ 限制驅導式生產排程在PCBA製程的運用	★ 平衡計分卡規劃與設計之研究-以海軍後勤支援指揮部修護工廠為例
★ 木製框式車身銷售數量之組合預測研究	★ 導入符合綠色產品RoHS之供應商管理-以光通訊產業L公司為例
★ 不同產品及供應商屬性對採購要求之相關性探討－以平面式觸控面板產業為例	★ 中長期產銷規劃之個案探討 -以抽絲產業為例
★ 消耗性部品存貨管理改善研究-以某邏輯測試公司之Socket Pin為例	★ 封裝廠之機台當機修復順序即時判別機制探討
★ 客戶危害限用物質規範研究-以TFT-LCD產業個案公司為例	★ PCB壓合代工業導入ISO/TS16949品質管理系統之研究-以K公司為例
★ 報價流程與價格議價之研究–以機殼產業為例	★ 產品量產前工程變更的分類機制與其可控制性探討-以某一手機產品家族為例

檔案

[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

推文