跳到主要內容

臺灣博碩士論文加值系統

(3.229.142.104) 您好!臺灣時間:2021/07/27 03:06
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:陳昱叡
研究生(外文):Yu-JuiChen
論文名稱:考量在流程式迴流生產環境下求解多訂單工作排程問題
論文名稱(外文):Solving multiple orders per job scheduling problem in re-entrant flowshop
指導教授:張秀雲張秀雲引用關係
指導教授(外文):Shiow-Yun Chang
學位類別:碩士
校院名稱:國立成功大學
系所名稱:工業與資訊管理學系碩博士班
學門:商業及管理學門
學類:其他商業及管理學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:98
中文關鍵詞:多訂單工作排程問題流程式迴流生產基因演算法NEH演算法GA-NEH演算法
外文關鍵詞:Multiple order per job scheduling problemReentrant flowshopGenetic algorithmNEH algorithmGA-NEH algorithm
相關次數:
  • 被引用被引用:1
  • 點閱點閱:237
  • 評分評分:
  • 下載下載:37
  • 收藏至我的研究室書目清單書目收藏:0
隨著資訊科技的進步以及積體電路技術的日新月異,市場對於晶圓的需求大幅度增加,因此晶圓製造商急切需要一個有效的派工法則以降低晶圓的生產週期時間。許多學者根據半導體的生產環境衍生出多訂單工作排程問題。所謂多訂單工作排程問題指的是晶圓製造商收到來自世界各地客戶的訂單,將其分派到各個晶圓傳送盒裡進行加工。訂單如何分配到各個晶圓傳送盒以及晶圓傳送盒的加工順序將會造成不同的完工時間,影響到晶圓生產的績效。考量到實際的晶圓生產過程,僅討論多訂單工作排程問題並無法反映真實的狀況,本研究參考數位學者的建議將流程式迴流生產環境加入到本研究中,流程式迴流生產為工作依照固定的加工順序並且重複進行加工的生產模式。流程式迴流生產環境下的多訂單工作排程問題雖然貼近現實生產狀況,但也提高問題的複雜性,所以無法在短時間內求出最佳解。因此本研究將以基因演算法、NEH演算法以及結合基因演算法和NEH演算法特性的GA-NEH演算法求出在可接受範圍內的近似解。
由數據可得知,多訂單工作排程問題在小筆加工作業數時,將訂單妥善安排至晶圓傳送盒比加工作業順序對完工時間的影響還要大;但當加工作業數逐步增加時,則加工作業順序比訂單安排更為重要。本研究運用基因演算法、NEH演算法以及GA-NEH演算法於具有流程式迴流生產特性的多訂單工作排程問題上,由於GA-NEH演算法綜合了基因演算法會將比較好的解保留起來以及NEH演算法能有效對加工作業做排序的特性,因此不管是在平均值或是最佳解的部分都要優於基因演算法以及NEH演算法,GA-NEH演算法能夠有效的求解在流程式迴流生產環境下的多訂單工作排程問題。
With the progression of information technology and integrated circuit technology, the demand of wafer has significantly increased, so the wafer manufacturers need an effective dispatching rules in order to reduce production cycle time of the wafers. In order to reflect the rapid increase of the semiconductor production environment, many scholars proposed the multiple orders per job scheduling problem. The multiple orders per job scheduling problem means that the wafer manufacturers receive orders from customers around the world, and in the production process, they assign orders to FOUPs by the orders’ attributes, then dispatch FOUPs by some dispatching rules, finally get the FOUPs’ completion time. But taking into consideration the actual wafer production process, only discuss the multiple order per job scheduling problem can not reflect the real situation, this study consider to include the reentrant flowshop environment to satisfy the real situation. And this study will use Genetic algorithm, NEH algorithm and GA-NEH algorithm to calculate the approximate solution within an acceptable range. Experiment data shows that, in small amount of orders, orders scheduling is more important than FOUPs scheduling on the impact to the FOUP’s completion time. But with amount of orders increasing, the FOUPs scheduling is more important. The result also shows that the performance of GA-NEH algorithm is better than Genetic algorithm and NEH algorithm.
摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 ix
第一章 緒論 1
1.1研究動機與目的 1
1.2研究範圍與假設 3
1.3研究流程 3
1.4論文架構 5
第二章 文獻探討 6
2.1多訂單工作的排程問題 6
2.2迴流生產排程問題 12
2.3多訂單工作排程結合迴流生產 14
2.4啟發式演算法 17
2.4.1基因演算法 17
2.4.2 NEH演算法 19
2.4.3 GA-NEH演算法 20
2.5 小結 22
第三章 模式建構 23
3.1 問題描述以及基本假設 23
3.2 符號定義以及模式建構 25
3.3 範例問題 28
3.3.1 訂單分開生產 29
3.3.2 訂單合併生產 29
3.3.3 混合式生產 30
3.4運用演算法於範例問題上 30
3.4.1 基因演算法 30
3.4.2 NEH演算法 35
3.4.3 GA-NEH演算法 38
3.5 最佳解驗證 39
3.6 小結 40
第四章 數據分析 41
4.1 實驗環境與參數 41
4.2 探討訂單安排和晶圓傳送盒加工順序的重要性 42
4.3 數據分析 55
4.4 程式執行時間 59
4.5 小結 59
第五章 結論與未來方向 61
5.1 結論 61
5.2 未來方向 61
參考文獻 63
附錄A 訂單安排和晶圓傳送盒加工順序的比較數據 67
附錄B 完工時間比較 94
附錄C 程式執行時間 97
中文文獻
吳建廣,「混合塔布搜尋法應用於具迴流特性流程工廠之研究」,國立台灣科技大
學工業管理系碩士論文,西元2003年。
林建民,「混合基因演算法應用於具迴流特性流程工廠之研究」,國立台灣科技大
學工業管理系碩士論文,西元2003年。
陳邑鑫,「考慮瓶頸作業下的排程方法」,南台科技大學工業管理研究所碩士論
文,西元2004年。

英文文獻
Chang, P.-C., Chen, S.-H., Fan, C.-Y., & Chan, C.-L. Genetic algorithm integrated with artificial chromosomes for multi-objective flowshop scheduling problems. Applied Mathematics and Computation, 205, 550–561, 2008.
Chen, J.-S. A branch and bound procedure for the reentrant permutation flow-shop scheduling problem. International Journal of Advanced Manufacturing Technology, 29, 1186–1193, 2006.
Chen, J.-S. Optimization model for scheduling jobs containing multiple orders on an unrelated parallel-machine. APIEMS2009, 2444–2452, 2009.
Chen, J.-S., Pan, J. C.-H., & Lin, C.-M. A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem. Expert Systems with Applications, 34, 570–577, 2008.
Chen, J.-S., Pan, J. C.-H., & Wu, C.-K. Minimizing makespan in reentrant flow-shops using hybrid tabu search. International Journal of Advanced Manufacturing Technology, 34, 353–361, 2007.
Choi, H.-S., Kim, H.-W., Lee, D.-H., Yoon, J., Yun, C. Y., & Chae, K. B. Scheduling algorithms for two-stage reentrant hybrid flow shops: minimizing makespan under the maximum allowable due dates. International Journal of Advanced Manufacturing Technology, 42, 963–973, 2009.
Choi, H.-S., Kim, J.-S., & Lee, D.-H. Real-time scheduling for reentrant hybrid flow shops: A decision tree based mechanism and its application to a TFT-LCD line. Expert Systems with Applications, 38, 3514–3521, 2011.
Choi, S.-W., & Kim, Y.-D. Minimizingmakespan on a two-machine re-entrant flowshop. Journal of the Operational Research Society, 58, 972–981, 2007.
Choi, S.-W., & Kim, Y.-D. Minimizing makespan on an m-machine re-entrant flowshop. Computers & Operations Research, 35, 1684–1696, 2008.
Chu, F., Chu, C., & Desprez, C. Series production in a basic re-entrant shop to minimize makespan or total flow time. Computers & Industrial Engineering, 58, 257–268, 2010.
Drobouchevitch, I. G., & Strusevich, V. A. A heuristic algorithm for two-machine re-entrant shop scheduling. Annals of Operations Research, 86, 417–439, 1999.
Erramilli, V., & Mason, S. J. Multiple orders per job compatible batch scheduling. IEEE Transactions on Electronics Packaging Manufacturing, 29, 285–296, 2006.
Erramilli, V., & Mason, S. J. Multiple orders per job batch scheduling with incompatible jobs. Annals of Operations Research, 159, 245–260, 2008,.
Glover, F. Tabu search—part I. ORSA Journal on Computing, 190–206, 1989.
Holland, J. A daptation in natural and artificial systems : an introductory analysis with applications to biology, control and artificial intelligence, 1975.
Jampani, J., & Mason, S. J. Column generation heuristics for multiple machine, multiple orders per job scheduling problems. Annals of Operations Research, 159, 261–273, 2008.
Jampani, J., & Mason, S. J. A column generation heuristic for complex job shop multiple orders per job scheduling. Computers & Industrial Engineering, 58, 108–118, 2010.
Jia, J., & Mason, S. J. Semiconductor manufacturing scheduling of jobs containing multiple orders on identical parallel machines. International Journal of Production Research, 47, 2565–2585, 2009.
Jing, C., Tang, G., & Qian, X. Heuristic algorithms for two machine re-entrant flow shop. Theoretical Computer Science, 400, 137–143, 2008.
Kayton, D. Using the theory of constraints’ production application in a semiconductor fab with a re-entrant Bottleneck. 1998 IEEE/CPMT Int’l Electronics Manufacturing Technology, 23, 352–357, 1998.


Kayton, D., Teyner, T., Schwartz, C., & Uzsoy, R. Effects of dispatching and down time on the performance of wafer fabs operating under theory of constraints. 1996 IEEE/CPMT Int’l Electronics Manufacturing Technology, 19, 49–56, 1996.
Kim, Y.-D., Kang, J.-H., Lee, G.-E., & Lim, S.-K. Scheduling algorithms for minimizing tardiness of orders at the burn-in workstation in a semiconductor manufacturing system. IEEE Transactions on Electronics Packaging Manufacturing, 24, 14–26, 2011.
Laub, J. D., Fowler, J. W., & Keha, A. B. Minimizing makespan with multiple-orders-per-job in a two-machine flowshop. European Journal of Operational Research, 182, 63–79, 2007.
Lee, C. K. M., Lin, D., Ho, W., & Wu, Z. Design of a genetic algorithm for bi-objective flow shop scheduling problems with re-entrant jobs. International Journal of Advanced Manufacturing Technology, 2011.
Liu, C.-H. A genetic algorithm based approach for scheduling of jobs containing multiple orders in a three-machine flowshop. International Journal of Production Research, 48, 4379–4396, 2010.
Mason, S. J., & Chen, J.-S. Scheduling multiple orders per job in a single machine to minimize total completion time. European Journal of Operational Research, 207, 70–77, 2010.
Mason, S. J., Qu, P., & Kutanoglu, E. The single machine multiple orders per job scheduling problem. IIE Transactions, 2004.
Nawaz, M., Jr, E. E. E., & Ham, I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91–95, 1983.
Pearn, W. L., Chung, S. H., Chen, Y., & Yang, M. H. A case study on the multistage IC final testing scheduling problem with reentry. International Journal of Production Economics, 88, 257–267, 2004.
Pinedo, M. L. Scheduling theory, algorithms and systems, 2001.
Qu, P., & Mason, S. J. Metaheuristic scheduling of 300-mm lots containing multiple orders. IEEE Transactions on Electronics Packaging Manufacturing, 18, 633–643, 2005.
Sobeyko, O., & Mönch, L. Genetuc algorithms to solve a single machine multiple orders per job scheduling problem. Proceedings of the 2010 Winter Simulation Conference, 2010.

Steiner, G., & Xue, Z. On the connection between a cyclic job shop and a reentrant flow shop scheduling problem. Journal of Scheduling, 9, 381–387, 2006.
Tanrisever, F., & Kutanoglu, E. Forming and scheduling jobs with capacitated containers in semiconductor manufacturing: Single machine problem. Annals of Operations Research, 159, 5–24, 2008.
Yang, D.-L., Kuo, W.-H., & Chern, M.-S. Multi-family scheduling in a two-machine reentrant flow shop with setups. European Journal of Operational Research, 187, 1160–1170, 2008.
Zimmermann, J., Mason, S. J., & Fowler, J. W. Determing an appropriate number of FOUPs in semiconductor wafer fabrication facilities. Proceedings of the 2008 Winter Simulation Conference, 2008.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top