An extension of NSGA-II approach for identical parallel machine with parallel batching and material assignment when minimizing makespan and total weighted material-wasted

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：177

、訪客IP：18.119.120.88

姓名

張登閎(Deng-Hong Zhang) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

(An extension of NSGA-II approach for identical parallel machine with parallel batching and material assignment when minimizing makespan and total weighted material-wasted)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2029-7-31以後開放)

摘要(中)

在半導體產業中，材料的分派及製程的時間控制非常重要，過多的材料浪費與時間消耗將會反映在生產成本上，因此我們針對等效平行機台排程問題(Identical Parallel scheduling problem)下，去考慮了決定哪些的材料組合要被裝載在機器上的材料分派(Material assignment)及平行批次處理(Parallel Batching)的子問題，並以最小化最晚完工時間(Minimum Makespan)以及最小化總加權材料浪費量(Minimum Total Weighted Material Wasted)為目標，期望能找到符合需求之優化排程。在我們的等效平行機台排程問題中，機台可行性(Machine eligibility)並不是預先給定好的，會隨著面對不同的作業的配方(Recipe)，材料需求組合會有所變化，在不同機台間可以同時進行加工，且不會彼此互相影響。我們使用了能夠表示批次處理的分離圖(Conjunctive graph)，並於圖形中同時呈現材料分配跟批次處理的結果。除了常見的弧屬性(Arc attribute)來表示時間(time)外，並在圖中多加了第二個弧屬性來表示剩餘材料數量(remaining consumption of each material )。利用這樣的表現方式，能夠利用最長路徑去對目標值去做計算。並針對兩種不同目標的最長路徑，建立其鄰域結構(Neighborhood structure)，由非支配排序基因演算法(Non-dominated Sorting Genetic Algorithm II, NSGA-II)，去求得雙目標的柏拉圖前緣(pareto front)，在每一次的迭代中找到適合留下來的子代，在有限的時間內求得優化解。

摘要(英)

In the semiconductor industry, the allocation of materials and control of processing time is crucial, as excessive material waste and time consumption will be reflected in production costs. Therefore, we address the Identical Parallel Scheduling Problem by considering the subproblems of material assignment, which determines which combinations of materials should be loaded onto machines, and parallel batching, aiming to minimize the makespan and the total weighted material waste. Our goal is to find an optimized schedule that meets these criteria.
In our Identical Parallel Scheduling Problem, machine eligibility is not predefined but varies based on different job recipes and material requirements. Processing can occur simultaneously across different machines without mutual interference. We employed a conjunctive graph to represent batch processing, incorporating both material allocation and batch processing results. Besides the common arc attribute representing time, we introduced a second arc attribute to represent the remaining consumption of each material. This representation allows us to compute objective values using the longest path.
We developed neighborhood structures for the crossover operator and mutation operator corresponding to the two different objectives. By utilizing the Non-dominated Sorting Genetic Algorithm II (NSGA-II), we derived the Pareto front for the bi-objective optimization problem, iteratively identifying suitable offspring to retain and obtaining an optimized solution within a limited time frame.

關鍵字(中)

★ 等效平行機台排程
★ 非支配排序遺傳驗算法-II
★ 柏拉圖前緣
★ 雙目標優化
★ 分離圖
★ 材料分派

關鍵字(英)

★ Identical parallel machine scheduling
★ NSGA-II
★ material assignment
★ Pareto front
★ bi-objective optimize
★ disjunctive graph

論文目次

摘要 I
Abstract ii
Table of Contents iii
List of Figures V
List of Tables VI
Chapter 1 Introduction 1
1.1 Research Motivation and Background 1
1.2 Problem Description 5
1.3 Research Objectives 6
1.4 Research Methodology 6
Chapter 2 Literature Review 12
2.1 Parallel Machine Scheduling Problem 12
2.2 Neighborhood Structure 14
2.3 Search Strategy 15
Chapter 3 Research Methodology 17
3.1 Conjunctive Graph Representation for Operations and Material Wasted 17
3.2 Generate the Initial Solutions 18
3.3 Crossover Operator 19
3.4 Mutation Operator 21
3.4.1 An Operation Move (Modified from Dauzère-Pérès & Jan Paulli (1997)) 21
3.4.2 Evaluation of Mutation Operator (moves) 22
3.5 Search Strategy 28
Chapter 4 Computational Result 33
4.1 Performance of Different Sizes of Dataset 35
4.2 Comparison the Performances of R classification and Random Selection 37
4.3 Comparison of the Impact of Crossover Utilization 37
Chapter 5 Conclusion 39
Acknowledgement 40
References 41
Appendix A An Example of the Crossover Operator 47
Step 1: Transform Parents′ Graph to the Chromosome 48
Step 2: Conduct the Crossover Operator 51
Step 3: Reassigning Operations to the Machine Periods in the Offspring 54
Step 4: Form the Offspring′s New Machine Processing Order 55
Appendix B Fast Non Dominated Sort 58
Appendix C Crowding-Distance-Assignment (?) 59
Appendix D Illustration of the Results of Two Objective Values Influenced by Six Boolean Conditions 60

參考文獻

Adams, G. R., Hicken, M., & Salehi, M. (1988). Socialization of the physical attractiveness stereotype: Parental expectations and verbal behaviors. International Journal of Psychology, 23(1-6), 137-149.
Akhbari M., 2022. “Integration of multi-mode resource-constrained project
scheduling under bonus-penalty policies with material ordering under quantity discount scheme for minimizing project cost.” Scientia Iranica E 29(1), 427-446.
Bagheri A., Zandieh M., 2011. “Bi-criteria flexible job-shop scheduling with sequence-dependent setup times - Variable neighborhood search approach.” Journal of Manufacturing Systems 30, 8-15.
Balas, E., & Vazacopoulos, A. (1998). Guided local search with shifting bottleneck for job shop scheduling. Management science, 44(2), 262-275.
Baykasoglu, A., Özbakır, L. “Analyzing the effect of dispatching rules on the scheduling performance through grammar-based flexible scheduling system.” International Journal of Production Economics 124, 369–381 (2010).
Bierwirth C., Kuhpfah J., 2017. “Extended GRASP for the Job Shop Scheduling Problem with Total Weighted Tardiness Objective.”. European Journal of Operational Research 261, 1-23.
Blazewicz, J., & Finke, G. (1994). “Scheduling with resource management in manufacturing systems”. European Journal of Operational Research, 1-14.
Braun, S., Peus, C., Weisweiler, S., & Frey, D. (2013). Transformational leadership, job satisfaction, and team performance: A multilevel mediation model of trust. The leadership quarterly, 24(1), 270-283.
Carlier, J., & Pinson, É. (1989). “An algorithm for solving the job-shop problem”. Management science, 35(2), 164-176.
Chaudhry, I. A., Khan, A. A research survey: review of flexible job shop scheduling techniques.
Chaves, A. A., Lorena, L. A. N., Senne, E. L. F., & Resende, M. G. (2016). Hybrid method with CS and BRKGA applied to the minimization of tool switches problem. Computers & Operations Research, 67, 174-183.
Coello Coello, C. A., & Cortés, N. C. (2005). “A study on the Inverted Generational Distance (IGD) indicator.” IEEE Transactions on Evolutionary Computation, 9(1), 58-67.
Dauzère-Pérès S., Paulli J., 1997. “An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search.” Annals of Operations Research 70, 281-306.
Dorndorf, U., & Pesch, E. (1995). Evolution based learning in a job shop scheduling environment. Computers & Operations Research, 22(1), 25-40.
Eshelman, L. J., & Schaffer, J. D. (1993). “Real-Coded Genetic Algorithms and Interval-Schemata”, Foundations of Genetic Algorithms, 187-202.
Garcia-Leon A. A., Dauzere-Peres S., Mati Y., 2019. “An efficient Pareto approach for solving the multi-objective flexible job-shop scheduling problem with regular criteria”. Computers and operations research 108 , 187-200.
Ghiani, C. A., Ying, Z., de Vellis, J., & Gomez-Pinilla, F. (2007). “Exercise decreases myelin-associated glycoprotein expression in the spinal cord and positively modulates neuronal growth”. Glia, 966–975.
Goh, C. K., & Tan, K. C. (2009). “Non-dominance ratio for preference articulation in evolutionary multiobjective optimization.” IEEE Transactions on Evolutionary Computation, 13(2), 347-365.
González M. A., Vela C. R., Varela R., 2015. “Scatter search with path relinking for the flexible job shop scheduling problem.” European Journal of Operational Research 245(1), 35-45.
Graham R. L., Lawler E. L., Lenstra J. K., and Rinnoo Kan A. H. G., 1979. “Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey.” Annals of Discrete Mathematics 5, 287–326.
Jensen, M.T. “Generating robust and flexible job shop schedules using genetic algorithms.” IEEE Transactions on Evolutionary Computation 7, 275–288 (2003).
Jia, S., Hu, Z.-H. “Path-relinking tabu search for the multi-objective flexible job shop scheduling problem.” Computers & Operations Research 47, 11–26 (2014).
Kim, Y.K., Park, K., Ko, J. “A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling.” Computers & Operations Research 30, 1151–1171 (2003).
K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II”, IEEE Transactions on Evolutionary Computation 6 (2) (2002) 182–197.
Knopp S., Dauzère-Pérès S., Yugma C., 2017. “A batch-oblivious approach for complex job-shop scheduling problems”. European Journal of Operational Research 263 (1), 50–61.
Kreipl, S. (2000). A large step random walk for minimizing total weighted tardiness in a job shop. Journal of Scheduling, 3(3), 125-138.
Kuo, Y.H., (2023). An extended batch-oblivious approach for flexible Job shop with batching and material consumption when minimizing the total weighted material consumed and makespan. Unpublished master’s thesis, National Central University, Taoyuan City.
Manne, A. S. (1960). On the job-shop scheduling problem. Operations research, 8(2), 219-223.
Mason, B. J., Goodman, A. M., Dixon, R. M., Hameed, M. H. A., Hulot, T., Wesnes, K., ... & Boyeson, M. G. (2002). A pharmacokinetic and pharmacodynamic drug interaction study of acamprosate and naltrexone. Neuropsychopharmacology, 27(4), 596-606.
Mati, B. M., Mutie, S., Gadain, H., Home, P., & Mtalo, F. (2008). Impacts of land‐use/cover changes on the hydrology of the transboundary Mara River, Kenya/Tanzania. Lakes & Reservoirs: Research & Management, 13(2), 169-177.
Mati Y., Dauzère-Pérès S., Lahlou C., 2011. “A general approach for optimizing regular criteria in the job-shop scheduling problem.” European Journal of Operational Research 212(1), 33-42.
Mecler, J., Subramaninan, A., & Vidal, T. (2021). “A simple and effective hybrid genetic search for the job sequencing and tool switching problem”. Computers and Operations Research.
Mönch, L., Fowler, J. W., Dauzère-Pérès, S., Mason, S. J., & Rose, O. (2011). A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations. Journal of scheduling, 14, 583-599.
Moradi, E., Fatemi Ghomi, S.M.T., Zandieh, M. “Bi-objective optimization research on integrated fixed time interval preventive maintenance and production for scheduling flexible job-shop problem.” Expert Systems with Applications 38, 7169–7178 (2011).
Mousakhani M., 2013. “Sequence-dependent setup time flexible job shop scheduling problem to minimize total tardiness.” International Journal of Production Research 51.12, 3476-3487.
Murovec, B. (2015). Job-shop local-search move evaluation without direct consideration of the criterion’s value. European Journal of Operational Research, 241(2), 320-329.
Muth, J. F., & Thompson, G. L. (1963). Industrial Scheduling. Englewood Cliffs, N. J., Prentice Hall 1963.
Nowicki E., Smutnicki C., 1996. “A fast taboo search algorithm for the job shop problem.”, Management Science 42, 797–813.
Peter Brucker and Rainer Schlie. (1990) “Job-shop scheduling with multi-purpose machines”. Computing 45, 369–375.
Pezzella, F., & Merelli, E. (2000). A tabu search method guided by shifting bottleneck for the job shop scheduling problem. European Journal of Operational Research, 120(2), 297-310.
Pezzella, F., Morganti, G., Ciaschetti, G. “A genetic algorithm for the flexible job-shop scheduling problem.” Computers & Operations Research 35, 3202–3212 (2008).
Privault, C., & Finke, G. (1995). “Modelling a tool switching problem on a single NC-machine”. Journal of Intelligent Manufacturing, 87–94.
Quang-Vinh Dang & Thijs van Diessen & Tugce Martagan & Ivo Adan,(2021).“A matheuristic for parallel machine scheduling with tool replacements”,European Journal of Operational Research,Vol. 291.
Rabiee, M., Zandieh, M., Ramezani, P. “Bi-objective partial flexible job shop scheduling problem: NSGA-II, NRGA, MOGA and PAES approaches.” International Journal of Production Research 50, 7327–7342 (2012).
Rahmati, S.H.A., Zandieh, M. “A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem.” International Journal of Advanced Manufacturing Technology 58, 1115–1129 (2011).
Rahmati, S.H.A., Zandieh, M., Yazdani, M. “Developing two multi-objective evolutionary algorithms for the multi-objective flexible job shop scheduling problem.” International Journal of Advanced Manufacturing Technology 64, 915–932 (2013).
Riquelme, J. C., Coello Coello, C. A., Montes Sánchez, G., & Mostaghim, S. (2015). “Interactive evolutionary multi-objective optimization based on Kriging models. ” Information Sciences 298, 139-155.
S. Elaoud, T. Loukil, J. Teghem. (2007), “The Pareto fitness genetic algorithm: Test function study”. European Journal of Operational Research, 1703-1719.
Shen L., Buscher U., 2012. “Solving the serial batching problem in job shop manufacturing systems”. European journal of operational research 221, 14-26.
Shen L., Dauzère-Pérès S., Neufeld J. S., 2017. “Solving the Flexible Job Shop Scheduling Problem with Sequence-Dependent Setup Times.” European journal of operational research 265, 503-516.
Snyman, S. & Bekker, J., (2019). “Comparing the performance of different metaheuristics when solving a stochastic bi-objective job shop scheduling problem.” In Proceedings of the 2019 ORSSA Annual Conference.
Van Laarhoven PJM., 1988. “Theoretical and computational aspects of simulated annealing.” PhD thesis, Erasmus University Rotterdam.
Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., & Rei, W. (2012). “A hybrid genetic algorithm for multidepot and periodic vehicle routing problems”. Operations Research, 60, 611–624.
Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2014). “A unified solution framework for multi-attribute vehicle routing problems.” European Journal of Operational Research, 234, 658–673.
Vilcot G., Billaut J. C., 2008. “A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem”. European journal of operational research 190, 389-411.
Wang, S., Yu, J. (2010). “An effective heuristic for flexible job-shop scheduling problem with maintenance activities”. Computers & Industrial Engineering, 436-447.
Wu, M. C., Lin, C. S., Lin, C. H., & Chen, C. F. (2017). “Effects of different chromosome representations in developing genetic algorithms to solve DFJS scheduling problems”, Computers & Operations Research, 101-112.
Yazdani, M., Amiri, M., Zandieh, M. “Flexible job-shop scheduling with parallel variable neighborhood search algorithm.” Expert Systems with Applications 37, 678–687 (2010).
Zhai, W., Kelly, P., & Gong, W. B. (1996). “Genetic algorithms with noisy fitness”. Mathematical and Computer Modelling, 131-142.
Zhang, H., Gen, M. “Multistage-based genetic algorithm for flexible job-shop
scheduling problem.” Journal of Complexity International 11, 223–232 (2005).
Zhou, H., Cheung, W., & Leung, L. C. (2009). Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm. European Journal of Operational Research, 194(3), 637-649.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2024-7-23

推文