集束型製程設備最佳排程之即時搜尋

Abstract

考慮集束型製程設備（Cluster Tool）的排程問題，可利用Petri Nets建構集束型製程設備模型，並藉由搜尋分析模型所產生的延展樹（reachability tree）來找出最佳排程。雖然搜尋得到的排程即為最佳，但往往需時數天才能找出結果。若以工業上實用的角度而言，上述搜尋排程法是不切實際的。 本論文使用即時啟發式搜尋法（Real-Time Heuristic Search）應用到上述之排程搜尋的問題上，以即時搜尋的方式獲得最佳或較佳的排程結果，並透過與離線式搜尋法所得之排程結果比較，來說明即時搜尋所得之排程時間，其搜尋結果與離線式搜尋法所得之排程時間幾乎相同。此外，亦比較即時搜尋法與離線搜尋法之兩者平均每步搜尋時間，利用即時搜尋法之平均每步搜尋時間並不會隨排程總處理程序的增加而增加。

Considering the optimal scheduling question of the Cluster Tool, which can use Petri Nets model to generate and search the reachability tree. But this method take much time in searching procedure. In the pratical use of industry, this solution is not proper. In this paper, we develop a method that aplly real-time heuristic searching algorithm to obtain optimal or near-optimal scheduling.To compare the spending time of our searching result and off-line searching result, they are almost equal. We also compare the searching time of real-time searching and off-line seaching algoristhm. The real-time searching time will not increase with the growth of scheduling procedure.