以節省法則為基礎之基因演算法求取批量平行機台最小化最大完工時間具機器合適度期間之排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：83

、訪客IP：18.218.196.21

姓名

黃宣甯(Syuan-Ning Huang) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

以節省法則為基礎之基因演算法求取批量平行機台最小化最大完工時間具機器合適度期間之排程問題
(A Saving Method-based Genetic Algorithm for Minimizing Makespan on Parallel Batch Processing with Machine Eligibility Period Determination)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

在半導體環境中，考慮 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.

關鍵字(中)

★ 批量平行機台
★ 物料限制
★ 時間窗口
★ 機器合適度
★ 基因演算法
★ 節省法則

關鍵字(英)

★ Parallel machine batch processing
★ Material constraints
★ Time window
★ Machine eligibility
★ Genetic Algorithm
★ Saving method

論文目次

摘要 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).

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2020-8-18

推文