我們在彈性零工式排程問題(flexible job shop scheduling problem)下考慮材料分配(material assignment)與批次處理(batching)的問題。決定哪些組合的化學材料要裝載在哪個機器上就是材料分配。而彈性零工式排程問題裡特有的機台可行性(Machine eligibility)在我們的環境中不是預先決定好、不變的，會隨著材料分配而變化。我們使用一種extended batch oblivious conjunctive graph來同時在分離圖(conjunctive graph)上同時呈現材料分配與批次處理。並且多加了第二個弧屬性(arc attribute)來表示消耗的加權材料總和(sum of total weighted material consumed)、第三個弧屬性表示材料分配。通過這樣的處理，我們除了可以得到常見的以時間為基礎的關鍵路徑(critical path)外，還可以有另一種基於消耗的加權材料總和的關鍵路徑。並基於這兩種關鍵路徑來定義鄰域結構(neighborhood structure)，以及引入重疊值(overlapping value)來幫助我們的搜索過程。我們還透過對移動(move)的估計函數(estimation function)將所以候選的移動(candidate moves)分類。還提出可以在兩條關鍵路徑與兩個目標中切換的搜索策略(search strategy)。實驗結果表明，我們可以通過搜索策略有效的使用兩種關鍵路徑，並配合有效的移動分類(move classification)來解決這種考慮材料分配的彈性零工式排程問題。;The studied problem considers material assignment and operation assignment simultaneously in a flexible job shop scheduling problem. The determination of a subset of materials loaded on a machine is the material assignment. Machine eligibility will change depending on the material assignment, different from conventional constant machine eligibility. An extended batch oblivious conjunctive graph is used to simultaneously represent the decision on the operation sequencing,batching and the decision on the material assignment. On each arc of the conjunctive graph, we attach the second arc attribute to represent the sum of weighted material consumed and the third arc attribute to represent material assignment. By using the conjunctive graph proposed, besides the critical path we commonly see on the literature which is time-based, we can have another type of critical path which is based on the sum of weighted material consumed. We propose an integrated move for our bi-objective problem, based on the two types of critical path to define the neighborhood structure. An overlapping value is introduced for sorting out the sequence of operations which will steer our improvement procedure. A move classification based on estimation function under two objectives is proposed to help select moves from candidates. A strategy alternately switching between objectives is proposed to provide a better diversification in the local search and give a better chance to find a good solution. The experimental results show that we can effectively use two types of critical paths by search strategy, and cooperate with effective move classification to solve this flexible job shop problem with material assignment.
