本研究主旨在探討零工式排程問題(job shop scheduling problem)下，考量材料限制(material constraint)以及批次處理(batching)的問題，目標為極小化最大完工時間(makespan)以及極小化total number of tardy stage-outs。在材料限制之下，當裝載在機器上的材料組合使用時間達到特定時長時，材料組合就必須進行更換。另外，我們建立了一個分離弧線圖(conjunctive graph)，其中每個工件(job)都具有多個層級(layer)，每個層級包含多個操作(operation)，而在層和層之間有額外的弧線去界定各層級的順序。在特定的層級的最後一個操作之後，我們新增了一個點並用弧線將此點與層級的最後一個操作相連，作為衡量該層級是否完工的依據。 針對研究的問題，我們使用了非支配排序遺傳演算法(NSGA-II)，除了修改前人的Job based Order Crossover(JOX)之外，也將原本隨機的變異過程改為使用局部搜索中的鄰域結構(neighborhood structure)取代。我們的鄰域結構會透過雙目標的關鍵路徑(critical path)所定義，以及引入偏好值來幫助我們的搜索過程。我們還會透過對移動(move)計算下限(lower bound)，並使用節省法(saving method)量化此移動對於雙目標的改善，以此作為選擇移動的依據。 ;The main purpose of this study is to investigate the Job Shop Scheduling Problem, taking into account material constraints and batching, with the objective of minimizing the maximum makespan and the total number of tardy stage-outs. Under material constraints, when the usage time of materials set which loaded on machine reaches certain limits, the materials set needs to be changed. Additionally, we have established a conjunctive graph where each job has multiple layers, each layer consists of multiple operations, and additional arcs are used to define the order of the layers. After the last operation in a specific layer, we add a node and connect it with an arc to the last operation in that layer to determine if that layer has completed. To address the research problem, we modified the Non-Dominated Sorting Genetic Algorithm (NSGA-II) by revising Job Based Order Crossover (JOX) and replacing the originally random mutation process with the neighborhood structure of local search. Our neighborhood structure is defined by critical paths of two objectives, and we introduce a preference value to aid in our search process. We also calculate lower bounds for moves and quantify the improvement of these moves on both objectives by using a saving method, which serves as the basis for selecting move.
