基於網路流模型之啟發式演算法求取具工件族與時間窗口限制之平行機台批次處理問題

、線上人數：8

、訪客IP：52.15.210.12

姓名	陳育萱(Yu-Syuan Chen) 查詢紙本館藏	畢業系所	工業管理研究所
論文名稱	基於網路流模型之啟發式演算法求取具工件族與時間窗口限制之平行機台批次處理問題 (A Network-flow-model Based Heuristic for Parallel Batch Processing Problem with Job Family and Time Window Constraints)
檔案	[Endnote RIS 格式] [Bibtex 格式] [相關文章] [文章引用] [完整記錄] [館藏目錄] 至系統瀏覽論文 (2026-1-1以後開放)
摘要(中)	在本研究中，我們考慮批次加工平行機台在群組與時間窗口限制下，求取極小化最大完工時間(????)之排程問題。本研究有數個工件可在平行機台上進行批次加工，且每個批次能放入的工件有數量的上限。因應半導體製程的特性，每個工件會依據不同的製程參數被分類成不同的群組，且只有相同群組的工件才能放在同一個批次中進行加工。在時間限制方面，由於每個工件抵達加工站時間不同，且根據製程參數中的時間限制，工件抵達工作站後在一定的時間內必須開始加工，否則該工件會被報廢且不可重工，本研究將依據此時間限制建立工件的時間窗口，限制其可加工時間。本研究首先使用網路流量分析方法(Network flow approach)，將排程問題轉換成網路流量問題，並建構相對應之網路流量模型，解決極小化最大完工時間之排程問題。接著將此結果應用至實務中，工件的操作時間具不可分割特性下之平行機台排程問題，透過搜尋一個鄰近最佳的可行解，以解決排程問題。
摘要(英)	In our research, we consider the scheduling problem of minimizing the maximum makespan (Cmax) for batch processing parallel machines with job family and time window constraints. There are n jobs can be batch processed on parallel machines, and there is an upper limit of the jobs that can be batched together. Because of the characteristics in the semiconductor manufacturing process, each job is grouped into different batches based on the different process parameters. Only using the same recipe jobs can be processed in the same batch. In terms of time limit, since each job arrives at the work station at a different time, and according to the time limit in the process parameters, the job must be processed within a certain time window after the job arrives at the work station. Otherwise, the job will be scrapped and cannot be reworked. In our research, we will set the time window of the job according to the time limit. In practice, parallel batch processing machine scheduling problem under the recipe and time window constraints is a common phenomenon in real life. In academical, we use network flow model as the lower bound in branch and bound algorithm to deal with the scheduling problem. First, we use the network flow approach to convert the scheduling problem into a network flow problem, and constructs a corresponding network flow model to solve the scheduling problem of minimizing the maximum makespan (Cmax). Then apply this result to the more general scheduling problem that job preemption is not allowed. Finally, we solve the scheduling problem by searching for a feasible solution.
關鍵字(中)	★ 排程 ★ 平行機台 ★ 批次加工 ★ 群組限制 ★ 時間窗口 ★ 最大完工時間 ★ 網路流量	關鍵字(英)	★ Scheduling ★ Parallel machines ★ Batch processing ★ Job family ★ Time window ★ Maximum makespan ★ Network flows
論文目次	摘要 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 description 2 1.3 Research objectives 3 1.4 Research methodology 4 1.5 Research framework 4 Chapter 2 Literature review 6 2.1 Batch processing parallel machine 6 2.2 Scheduling problems with job family constraint 7 2.3 Time window constraints 8 2.4 Network flow approach 8 Chapter 3 Methodology 10 3.1 Notations 10 3.2 Network flow model 12 3.2.1 Batch formation and the powerset 12 3.2.2 Obtain the time epoch set and the time windows 13 3.2.3 Construct network flow model 1 14 3.2.4 Construct network flow model 2 20 3.2.5 The relationship between model 1 and model 2 24 3.2.6 Binary Search to get a solution 24 3.3 Search for a feasible solution 25 Chapter 4 Computational Analysis 28 4.1 Test problem generation 28 4.2 Validation of the network flow model 29 4.3 Performance evaluation 31 4.4 Experiment for large-size instances 33 Chapter 5 Conclusion 35 5.1 Research contribution 35 5.2 Research limitation 35 5.3 Further research 36 References 37
參考文獻	[1]Kashan, A. H., Karimi, B. & Jenabi, M. (2006), A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes. Computers & Industrial Engineering, 1084-1098. [2]Ahmadi, J. H., Ahmadi, R. H., Dasu, S. & Tang, C. S. (1992), Batching and Scheduling Jobs on Batch and Discrete Processors. Operations Research, 40(4), 750–763. [3]Nguyen, A. H. G. (2020), Scheduling a Parallel Batch Processing Problem with Machine Eligibility Determination and Time Window Constraint. Working paper, the Institute of Industrial Management, National Central University. [4]Chang P.-Y., Damodaran P. & Melouk, S. (2004), Minimizing makespan on parallel batch processing machines. International Journal of Production Research 42(19):4211-4220. [5]Cheng, B., Cai, J., Yang, S. & Hu, X. (2014), Algorithms for scheduling incompatible job families on single batching machine with limited capacity. Computers and Industrial Engineering, 75(1), 116–120. [6]Graham, R. L., Lawler, E. L., Lenstra, J. K. & Rinnooy Kan, A. H. G. (1979), Optimization and approximation in deterministic machine scheduling: a survey. Annals of Discrete Mathematics, 5, 287–326. [7]Li, S. (1997), A hybrid two-stage flowshop with part family, batch production, major and minor set-ups. European Journal of Operational Research, 102(1), 142–156. [8]Liao, L. W. & Sheen, G. J. (2008), Parallel machines scheduling with machine availability and eligibility constraints. European Journal of Operational Research, 184(2), 458-467. [9]Li X., Yalaoui F. & Amodeo L. (2010), A multi objective meta-heuristic with a fuzzy logic controller for solving a scheduling problem. Computational intelligence: foundations and applications: proceedings of the 9th international FLINS conference, Emei, CHINA, August 02-04. [10]Pinedo, M. L. (2009), Planning and scheduling in manufacturing and services. Springer, New York. [11]Su, L. H. (2003), A hybrid two-stage flow shop with limited waiting time constraints. Computers & Industrial Engineering, 44(3), 409-424. [12]Sung, C. S., Choung, Y. I., Hong, J. M. & Kim, Y. H. (2002), Minimizing makespan on a single burn-in oven with job families and dynamic job arrivals. Computers and Operations Research, 29(8), 995–1007. [13]Tu, Y. M. & Liou, C. S. (2006), Capacity determination model with time constraints and batch processing in semiconductor wafer fabrication. Journal of the Chinese Institute of Industrial Engineers, 23(3), 192-199. [14]Webster, S. & Baker, K. R. (1995), Scheduling groups of jobs on a single machine. In Operations Research (Vol. 43, Issue 4, pp. 692–703). [15]Xu, R., Chen, H. & Li, X. (2012), Makespan minimization on single batch-processing machine via ant colony optimization. Comput. Oper. Res. 39 (3), 582-593.
指導教授	沈國基葉英傑(Gwo-Ji Sheen Ying-Chieh Yeh)	審核日期	2021-7-14
推文	facebook plurk twitter funp google live udn HD myshare reddit netvibes friend youpush delicious baidu
網路書籤	Google bookmarks del.icio.us hemidemi myshare

博碩士論文 108426005 詳細資訊