我們在 Job family 特性的柔性作業車間調度問題(Flexible job shop scheduling problem)下，考慮材料分配(Material assignment)以及批次處理(Batching)的問題，目標為極小化最大完工時間(Makespan)以及極小化總加權物料浪費(Sum of total weighted material-wasted)。決定哪些的材料組合要裝載在機器上去做操作就是材料分配。而在柔性作業車間調度問題中特有的機台可行性(Machine eligibility)以及考慮到在我們的環境中並不是預先決定好、不變的，會隨著不同的作業的配方(Recipe)中的材料分配組合有所變化。我們使用了Batch oblivious conjunctive graph 的方式來建構分離圖(Conjunctive graph)，以同時呈現材料分配跟批次處理的結果。除了常見的弧屬性(Arc attribute)來表示時間(Time)外，並在圖中多加了第二個弧屬性(Arc attribute)來表示每一個物料個別的剩餘量(Remaining package size for each material)。 通過這樣的處理，我們除了可以得到常見的以時間為基礎的關鍵路徑(Critical path)外，還可以衍生出另一種基於浪費的加權材料總和的關鍵路徑。針對研究的問題，我們使用了非支配排序遺傳演算法(NSGA-II)，除了延伸前人Crossover operator之外，也將原本隨機的變異過程改為使用上述兩種關鍵路徑來定義鄰域結構(Neighborhood structure)取代，以及引入重疊值(Overlapping value)來幫助我們的搜索過程。我們還透過對移動(Move)的實際值評估將候選的移動(Candidate move)做分類，以此作為選擇移動的依據。;This study aims to address the Flexible Job Shop Scheduling Problem (FJSP) with job family by incorporating considerations for material assignment and parallel batching considerations, with the objective of minimizing the maximum makespan and the sum of weighted material-wasted. Material assignment involves deciding which combinations of materials to load onto machines for operations. In our scenario, machine eligibility is not predetermined but varies with different material assignment combinations, depending on the recipes for various operations. To represent the decision on the operation sequencing, batching and the decision on the material assignment simultaneously, we employ an Extended Batch Oblivious Conjunctive Graph (EBOCG). The EBOCG incorporates several arc attributes to capture essential information. On each arc of the conjunctive arc, we attach the second arc attribute to represent the remaining package size for each material. By employing the proposed conjunctive graph, in addition to the conventional time-based critical path commonly discussed in the literature, we can derive another type of critical path which is based on the sum of weighted material-wasted. To address the research problem, we employ the Non-dominated Sorting Genetic Algorithm II (NSGA-II). Beyond extending the crossover operator from previous works, we modify the original random mutation process by defining neighborhood structures using the aforementioned critical paths and introducing an overlapping value to aid the search process. Furthermore, we classify candidate moves based on the evaluation of actual move values, using this classification as the basis for move selection.
