在本研究中，我們考慮單一機台批次處理在就緒時間、不同作業大小和不兼容的作業族之排程問題。目標是使用分支定界演算法求取最小化的總完工時間。本項研究中，多個工件被設置為在同台機器上進行批次加工。因應半導體製造以下幾個特徵 : 批處理，配方，作業到達時間。批處理表示同時加工多個作業。配方記錄每一個作業的過程參數，例如時間，溫度，濕度，化學限制等。具有相同配方的作業具有同樣的加工時間，並且可以在同個批次中同時進行加工。在作業抵達的時間方面，每一個工件抵達加工站的時間不一定相同。本研究依據這些特性發展分支定界演算法來求取最小總完工時間之問題。 我們將工件依據使用的配方進行分組以縮小問題範圍，並製定搜尋策略來決定如何探索節點。一個好的搜尋策略可以改善搜尋的效率以更快地找到最優解。除此之外，我們提出了一些命題，這些命題也可以用來提高算法的效率。我們發展的分支定界演算法，將在隨機產生的問題實例上進行測試。 ;In our research, we think out the scheduling problem about a single batch processing machine with release time, incompatible job families and different job sizes；our main purpose is to minimize total completion time. In our research, we suppose a set of n jobs to be processed in batches on single machine. In response to the following characteristics of semiconductor manufacturing: batch processing machine, size of jobs, recipe, job arrival time. As long as the total size of the jobs in the batch does not exceed the maximum batch capacity, the batch machine can process multiple jobs simultaneously. The recipe records the process parameters of each job. Only jobs of the same recipe can be put into the same batch to process and jobs from same recipe with same processing time. In terms of job arrival time, each job does not necessarily arrive at the processing station at the same time. Based on these characteristics, this research develops a branch and bound algorithm to find the minimal total completion time of the problem. We develop the batching method to narrow the scope of the problem and develop the searching strategy to decide how to explore nodes. A good searching strategy can help us find the optimal solution quicker and may increase the algorithm efficiency. Furthermore, we purpose several propositions that are also use to improve the efficiency of algorithm. Finally, in the computational experiment, we will test the branch and bound algorithm we proposed on randomly generated problem instances.
