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

NCUIR > School of Management at National Central University > Graduate Institute of Industrial Management > Electronic Thesis & Dissertation > Item 987654321/94565

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/94565

Title:	An extension of NSGA-II approach for identical parallel machine with parallel batching and material assignment when minimizing makespan and total weighted material-wasted
Authors:	張登閎;Zhang, Deng-Hong
Contributors:	工業管理研究所
Keywords:	等效平行機台排程;非支配排序遺傳驗算法-II;柏拉圖前緣;雙目標優化;分離圖;材料分派;Identical parallel machine scheduling;NSGA-II;material assignment;Pareto front;bi-objective optimize;disjunctive graph
Date:	2024-07-23
Issue Date:	2024-10-09 15:16:51 (UTC+8)
Publisher:	國立中央大學
Abstract:	在半導體產業中，材料的分派及製程的時間控制非常重要，過多的材料浪費與時間消耗將會反映在生產成本上，因此我們針對等效平行機台排程問題(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.
Appears in Collections:	[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	49	View/Open

社群 sharing

Loading...