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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:黃宣甯
研究生(外文):Syuan-Ning Huang
論文名稱:以節省法則為基礎之基因演算法求取批量平行機台最小化最大完工時間具機器合適度期間之排程問題
論文名稱(外文):A Saving Method-based Genetic Algorithm for Minimizing Makespan on Parallel Batch Processing with Machine Eligibility Period Determination
指導教授:沈國基沈國基引用關係
指導教授(外文):Gwo-Ji Sheen
學位類別:碩士
校院名稱:國立中央大學
系所名稱:工業管理研究所
學門:商業及管理學門
學類:其他商業及管理學類
論文出版年:2020
畢業學年度:108
語文別:英文
論文頁數:87
中文關鍵詞:批量平行機台物料限制時間窗口機器合適度基因演算法節省法則
外文關鍵詞:Parallel machine batch processingMaterial constraintsTime windowMachine eligibilityGenetic AlgorithmSaving method
相關次數:
  • 被引用被引用:0
  • 點閱點閱:38
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在半導體環境中,考慮 n 個不可被分割的工件及 m 台平行機台的排程問題,根據每個工件都有不同的加工配方,相同的配方才可以做批量加工,而每一個批量加工的時間為該批量中加工時間最長的工件。我們針對每台機台對於配方裝載具有機器合適度,且不同工件會有時間上的限制,必須在一定時間內加工完畢,否則產生報廢現象,造成製程成本上的負擔。因此我們的研究目標是在這些環境條件限制下找出最小化最大完工時間,且減少總物料浪費。
為了求出此問題的解,本研究方法以基因演算法為底,加上傳統派車問題中的節省法,在染色體架構上結合批量特性及機器合適度,改良前人所研究的交換及突變理論,並加入節省法則於演算法中。接著以混整數規劃來比較傳統基因演算法及結合節省法則的基因演算法,探討在統計上是否有顯著效果。
根據研究我們發現在小問題的排程環境中並不會使結合節省法則之基因演算法造成顯著上的差異,但在大問題的排程環境中,有節省法則的基因演算法有效降低了完工時間及物料浪費,也因此找出更佳解。
In the semiconductor environment, consider the scheduling of n jobs and m parallel machines. Each job has a different recipe, the same recipe can be batched together, and the batch processing time is given by the longest job processing time included in the batch processing. We have machine eligibility for each machine, and different jobs will have time window constraints, they must be processed within a certain time, otherwise scrapping will occur, causing a burden on the process cost. Therefore, our research objective is to find the minimum makespan under these environmental conditions and reduce the total waste of material.
In order to find a solution to this problem, this research methodology is based on genetic algorithm, coupled with the saving method in the traditional car dispatching problem, combined with batch characteristics and machine eligibility on the chromosome structure, and improved the crossover and mutation researches studied by previous researchers and add the saving method to the algorithm. Then we use mixed integer programming to compare the traditional genetic algorithm and the saving based genetic algorithm. Finally, we explore whether there is a statistically significant effect.
According to research, we found that in the scheduling environment of small problems, the saving based genetic algorithm will not cause a significant difference, but in the scheduling environment of the big problem, the saving based genetic algorithm effectively reduces the makespan and materials were wasted, so a better solution was found.
摘要 i
Abstract ii
Contents iii
List of Figures v
List of Tables vii
Chapter 1 Introduction 1
1.1 Research background and motivation 1
1.2 Problem definition 3
1.3 Research objective 8
1.4 Research methodology 8
1.5 Research framework 9
Chapter 2 Literature Review 11
2.1 Machine eligibility constraint 12
2.2 Time window constraint 13
2.3 Parallel machine batch processing 14
2.4 Genetic Algorithm 17
2.4.1 Chromosome 18
2.4.2 Crossover 19
2.4.3 Mutation 21
2.5 Saving method 22
Chapter 3 Methodology 23
3.1 Notation 23
3.2 The genetic algorithm 25
3.2.1 Encoding 27
3.2.2 Chromosome decoding 29
3.2.3 Initial population 30
3.2.4 Fitness function 30
3.2.5 Crossover 30
3.2.6 Mutation 31
3.3 Saving Method-based Genetic Algorithm 33
Chapter 4 Computational Analysis 38
4.1 Test problem generation 38
4.2 Validation of the Genetic Algorithm 39
4.3 Performance of the Genetic Algorithm 42
4.3.1 Maximum size of instance 53
Chapter 5 Conclusion 57
5.1 Research Contribution 57
5.2 Research Limitation 58
5.3 Further Research 58
References 59
Appendix 64
Adan, J., A.Akcay, J.Stokkermans, and R.Van den Dobbelsteen. (2018). “A Hybrid Genetic Algorithm for Parallel Machine Scheduling at Semiconductor Back-End Production.” Proceedings International Conference on Automated Planning and Scheduling, ICAPS 2018-June(Icaps):298–302.
[2] Afzalirad, Mojtaba and Javad Rezaeian. (2016). “Resource-Constrained Unrelated Parallel Machine Scheduling Problem with Sequence Dependent Setup Times, Precedence Constraints and Machine Eligibility Restrictions.” Computers and Industrial Engineering 98:40–52.
[3] Afzalirad, Mojtaba and Masoud Shafipour. (2015). “Design of an Efficient Genetic Algorithm for Resource-Constrained Unrelated Parallel Machine Scheduling Problem with Machine Eligibility Restrictions.” Journal of Intelligent Manufacturing 29(2):423–37.
[4] Anh, Hang Giang Nguyen (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.
[5] Balasubramanian, Hari, Lars Mönch, John Fowler, and Michele Pfund. (2004). “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–38.
[6] Belkaid, F., Z.Sari, and F.Yalaoui. (2013). “A Hybrid Genetic Algorithm for Parallel Machine Scheduling Problem with Consumable Resources.” 2013 International Conference on Control, Decision and Information Technologies, CoDIT 2013 143–48.
[7] Belkaid, Fayçal, ZakiSari, and Mehdi Souier. (2013). “A Genetic Algorithm for the Parallel Machine Scheduling Problem with Consumable Resources.” International Journal of Applied Metaheuristic Computing 4(2):17–30.
[1] Adan, J., A.Akcay, J.Stokkermans, and R.Van den Dobbelsteen. (2018). “A Hybrid Genetic Algorithm for Parallel Machine Scheduling at Semiconductor Back-End Production.” Proceedings International Conference on Automated Planning and Scheduling, ICAPS 2018-June(Icaps):298–302.
[2] Afzalirad, Mojtaba and Javad Rezaeian. (2016). “Resource-Constrained Unrelated Parallel Machine Scheduling Problem with Sequence Dependent Setup Times, Precedence Constraints and Machine Eligibility Restrictions.” Computers and Industrial Engineering 98:40–52.
[3] Afzalirad, Mojtaba and Masoud Shafipour. (2015). “Design of an Efficient Genetic Algorithm for Resource-Constrained Unrelated Parallel Machine Scheduling Problem with Machine Eligibility Restrictions.” Journal of Intelligent Manufacturing 29(2):423–37.
[4] Anh, Hang Giang Nguyen (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.
[5] Balasubramanian, Hari, Lars Mönch, John Fowler, and Michele Pfund. (2004). “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–38.
[6] Belkaid, F., Z.Sari, and F.Yalaoui. (2013). “A Hybrid Genetic Algorithm for Parallel Machine Scheduling Problem with Consumable Resources.” 2013 International Conference on Control, Decision and Information Technologies, CoDIT 2013 143–48.
[7] Belkaid, Fayçal, ZakiSari, and Mehdi Souier. (2013). “A Genetic Algorithm for the Parallel Machine Scheduling Problem with Consumable Resources.” International Journal of Applied Metaheuristic Computing 4(2):17–30.
[8] Belkaid, Fayçal, Farouk Yalaoui, and Zaki Sari. (2017). “Investigations on Genetic Algorithm Performances in a Parallel Machines Scheduling Environment.” The Open Automation and Control Systems Journal 9(Suppl-1, M6):60–74.
[9] Brucker, Peter and Svetlana A.Kravchenko. (2008). “Scheduling Jobs with Equal Processing Times and Time Windows on Identical Parallel Machines.” Journal of Scheduling 11(4):229–37.
[10] Centeno, Grissele and Robert L.Armacost. (2004). “Minimizing Makespan on Parallel Machines with Release Time and Machine Eligibility Restrictions.” International Journal of Production Research 42(6):1243–56.
[11] Centeno, Grisselle and Robert L.Armacost. (1997). “Parallel Machine Scheduling with Release Time and Machine Eligibility Restrictions.” Computers and Industrial Engineering 33(1–2):273–76.
[12] Chaudhry, Imran Ali. (2010). “Minimizing Flow Time for the Worker Assignment Problem in Identical Parallel Machine Models Using GA.” International Journal of Advanced Manufacturing Technology 48(5–8):747–60.
[13] Chen, Huaping, Bing Du, and George Q.Huang. (2011). “Scheduling a Batch Processing Machine with Non-Identical Job Sizes : A Clustering Perspective.” (October 2014):37–41.
[14] Cheng, Bayi, Shanlin Yang, Xiaoxuan Hu, and Bo Chen. (2012). “Minimizing Makespan and Total Completion Time for Parallel Batch Processing Machines with Non-Identical Job Sizes.” Applied Mathematical Modelling 36(7):3161–67.
[15] Clarke, G. and J. W.Wright. (1964). “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points.” Operations Research 12(4):568–81.
[16] Damodaran, Purushothaman, Neal S.Hirani, and Mario C.Velez-Gallego. (2009). “Scheduling Identical Parallel Batch Processing Machines to Minimise Makespan Using Genetic Algorithms.” European Journal of Industrial Engineering 3(2):187–206.
[17] Damodaran, Purushothaman, Praveen Kumar Manjeshwar, and Krishnaswami Srihari. (2006). “Minimizing Makespan on a Batch-Processing Machine with Non-Identical Job Sizes Using Genetic Algorithms.” International Journal of Production Economics 103(2):882–91.
[18] Fowler, John W., Shwu MinHorng, and Jeffery K.Cochran. (2003). “A Hybridized Genetic Algorithm to Solve Parallel Machine Scheduling Problems with Sequence Dependent Setups.” International Journal of Industrial Engineering : Theory Applications and Practice 10(3):232–43.
[19] Hamidinia, Amir, Sahand Khakabimamaghani, Mohammad Mahdavi Mazdeh, andMostafaJafari. (2012). “A Genetic Algorithm for Minimizing Total Tardiness/Earliness of Weighted Jobs in a Batched Delivery System.” Computers and Industrial Engineering 62(1):29–38.
[20] Kadri, Roubila Lilia and Fayez F.Boctor. (2018). “An Efficient Genetic Algorithm to Solve the Resource-Constrained Project Scheduling Problem with Transfer Times: The Single Mode Case.” European Journal of Operational Research 265(2):454–62.
[21] Kurniawan, B., A.Gozali, W.Weng, and S.Fujimura. (2017). “A Genetic Algorithm for Unrelated Parallel Machine Scheduling Minimizing Makespan Cost and Electricity Cost Under Time-of-Use(TOU) Tariffs with Job Delay Mechanism.” IEEE Industrial Engineering and Engineering Management Conference 583–87.
[22] Li, Xiaohui, Farouk Yalaoui, Lionel Amodeo, and Hicham Chehade. n.d. (2010). “A MULTIOBJECTIVE METAHEURISTIC WITH A FUZZY.” 276–81.
[23] Li, Yanzhi, FanWang, and AndrewLim. (2003). “Resource Constraints Machine Scheduling: A Genetic Algorithm Approach.” 2003 Congress on Evolutionary Computation, CEC 2003 - Proceedings 2:1080–85.
[24] Malve, Sujay and Reha Uzsoy. (2007). “A Genetic Algorithm for Minimizing Maximum Lateness on Parallel Identical Batch Processing Machines with Dynamic Job Arrivals and Incompatible Job Families.” Computers and Operations Research 34(10):3016–28.
[25] Min, Liu and Wu Cheng. (1999). “A Genetic Algorithm for Minimizing the Makespan in the Case of Scheduling Identical Parallel Machines.” Artificial Intelligence in Engineering 13(4):399–403.
[26] Mönch, Lars, Hari Balasubramanian, John W.Fowler, and Michele E.Pfund. (2005). “Heuristic Scheduling of Jobs on Parallel Batch Machines with Incompatible Job Families and Unequal Ready Times.” Computers and Operations Research 32(11):2731–50.
[27] Mönch, Lars, John W.Fowler, Stéphane Dauzère-Pérès, Scott J.Mason, and OliverRose. (2011). “A Survey of Problems, Solution Techniques, and Future Challenges in Scheduling Semiconductor Manufacturing Operations.” Journal of Scheduling 14(6):583–99.
[28] Nearchou, Andreas C. (2004). “The Effect of Various Operators on the Genetic Search for Large Scheduling Problems.” International Journal of Production Economics 88(2):191–203.
[29] Pearn, W. L., J. S.Hong, and Y. T.Tai. (2013). “The Burn-in Test Scheduling Problem with Batch Dependent Processing Time and Sequence Dependent Setup Time.” International Journal of Production Research 51(6):1694–1706.
[30] Potts, Chris N. and Mikhail Y.Kovalyov. (2000). “Scheduling with Batching: A Review.” European Journal of Operational Research 120(2):228–49.
[31] Rand, GK. (2009). “The Life and Times of the Savings Method for Vehicle Routing Problems.” ORiON 25(2):125–45.
[32] Saidi-Mehrabad, Mohammad and Samira Bairamzadeh. (2018). “Design of a Hybrid Genetic Algorithm for Parallel Machines Scheduling to Minimize Job Tardiness and Machine Deteriorating Costs with Deteriorating Jobs in a Batched Delivery System.” Journal of Optimization in Industrial Engineering 11(1):35–50.
[33] Sheen, Gwo Ji, Lu WenLiao, and Cheng FengLin. (2008). “Optimal Parallel Machines Scheduling with Machine Availability and Eligibility Constraints.” International Journal of Advanced Manufacturing Technology 36(1–2):132–39.
[34] Su, Ling Huey. (2003). “A Hybrid Two-Stage Flowshop with Limited Waiting Time Constraints.” Computers and Industrial Engineering 44(3):409–24.
[35] Tu, Ying Mei and Chuen ShiuanLiou. (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–99.
[36] Wang, Hung Kai, Chen Fu Chien, and MitsuoGen. (2015). “An Algorithm of Multi-Subpopulation Parameters with Hybrid Estimation of Distribution for Semiconductor Scheduling with Constrained Waiting Time.” IEEE Transactions on Semiconductor Manufacturing 28(3):353–66.
[37] Wilson, A. D., R. E.King, and T. J.Hodgson. (2004). “Scheduling Non-Similar Groups on a Flow Line: Multiple Group Setups.” Robotics and Computer-Integrated Manufacturing 20(6 SPEC. ISS.):505–15.
[38] Zhang, Bin, DaweiWu, Yingjie Song, KeweiLiu, and JuxiaXiong. (2020). “A Novel Fast Parallel Batch Scheduling Algorithm for Solving the Independent Job Problem.” Applied Sciences (Switzerland) 10(2):1–17.
[39] Zhang, Rui. (2017). “Sustainable Scheduling of Cloth Production Processes by Multi-Objective Genetic Algorithm with Tabu-Enhanced Local Search.” Sustainability (Switzerland) 9(10).
電子全文 電子全文(網際網路公開日期:20230731)
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔