在半導體製程中，我們在彈性零工式排程問題(Flexible job shop scheduling problem)環境下，考慮的限制條件有批次處理(Batching)和順序相依整備時間 (Sequence-dependent setup time)，目標為最小化總延遲時間(Total tardiness)和 Total number of tardy stage-outs。這兩個目標的解可以通過分離圖(Conjunctive graph)來表示，其中每個工件(job)都具有多個層級(layer)，每個層級包含多個操作 (operation)，且總延遲階段數的目標會以圖層(layer)的方式呈現。為解決這一雙目 標問題，本研究採用了NSGA-II演算法作為基於帕累托(Pareto-based)的方法來尋找最 佳解。鄰域結構(Neighborhood structure)將被應用於突變運算子(Mutation operator)，並且包括兩種類型的移動(Move)，以及引入偏好值(preference value)來 幫助我們的搜索過程。這些移動的可行性保證(Feasibility guarantees)將確保在移 動後不會產生循環(Cycle)。此外，我們將提出針對兩個目標值新的下界(New Lower bounds)將確保在進行移動後不會增加目標值，並將利用新的下界和節省值(saving values)改善階層式移動分類(Hierarchy of moves)結果且應用於增強解的多樣性與效 果。;In the semiconductor manufacturing process, we consider the Flexible Job Shop Scheduling Problem (FJSP) environment with two specific constraints: batch processing and sequence-dependent setup times. The objective is to minimize both the total tardiness and the total number of tardy stage-outs. Solutions for these two objectives can be represented using a conjunctive graph, where each job has multiple layers, each layer consists of multiple operations, and the objective of minimizing the number of tardy stage-outs is visualized through layered graph structures. To address this bi-objective optimization problem, we adopt the NSGA-II algorithm, a Pareto-based evolutionary approach for identifying optimal solutions. A neighborhood structure is applied within the mutation operator, incorporating two types of moves along with a preference value to guide the search process. The feasibility of these moves is guaranteed to prevent the creation of cycles in the graph. Moreover, we introduce new lower bounds for both objective functions to ensure that moves do not worsen the objective values after being applied. These new bounds, along with associated saving values, are used to improve the hierarchy of move classifications, thereby enhancing both solution diversity and solution quality.
