1.2.3　調度方法

目前,調度方法可以歸納為三類:基于運籌學的方法,基于啟發式規則的方法,基于人工智能、計算智能和群體智能的方法。

(1)基于運籌學的方法

該方法是將生產調度問題轉化為數學規劃模型,采用基于枚舉思想的分支定界法或動態規劃算法求解調度問題的最優解或近似最優解,屬于精確算法。對于生產特點有別于傳統的job?shop和flow?shop的半導體晶圓制造業,這種純數學方法有模型抽取困難、運算量大、算法難以實現等弱點。

(2)基于啟發式規則的方法

啟發式規則是指選取工件的某個或者某些屬性作為工件的優先級,按照優先級高低選擇工件進行加工。根據調度目標的不同,半導體制造過程啟發式規則可以分為基于交貨期的規則、基于加工周期的規則、基于工件等待時間的規則、基于工件使用程序是否相同的規則和基于負載平衡的規則。啟發式規則以其簡單性和快速性成為實際半導體制造環境下動態調度的首選,但也有一定的局限性,比如只能提高產品的個別性能指標,對生產線的整體性能提高能力較弱。

由于半導體制造過程的調度優化是個非常復雜的問題,其性能好壞不僅取決于調度策略本身,而且和系統模型、處理時間的方差、實際平均加工周期與理論加工周期有關,與系統中瓶頸設備個數、需重復訪問次數、緊急訂單加入等因素也有著十分密切的聯系。盡管啟發式規則計算量小、效率高、實時性好,但是它通常僅對一個或多個目標提供可行解,缺乏對整體性能的有效把握和預見能力,其調度結果可能會與系統的全局優化有較大的偏差。因此,啟發式規則通常需要與智能方法結合使用,根據系統狀態在備選規則間進行選擇。典型的研究方法通常是將智能方法、仿真方法和啟發式規則相結合。

(3)基于人工智能、計算智能和群體智能的方法

人工智能也稱機器智能,它是計算機科學、控制論、信息論、神經生理學、心理學、語言學等多種學科互相滲透而發展起來的一門綜合性學科。在半導體調度算法中常用的人工智能系統有專家系統和人工神經網絡等,其中人工神經網絡通常與其他方法(比如動態規劃)結合起來運用。

計算智能以人類、生物的行為方式或物質的運動形態為背景,經過數學抽象建立算法模型,通過計算機的計算來求解組合最優化問題。常用的計算智能有禁忌搜索、模擬退火、遺傳算法、人工免疫算法等。在半導體制造系統調度中,既可以使用單獨的某種計算智能方法,也可以將不同的計算智能算法相結合或將計算智能算法與建模技術相結合共同解決調度難題,以獲得更好的性能。

群體智能是受啟發于群居生物的群體行為并模擬抽象而成的算法和模型,在沒有集中控制且不提供全局模型的前提下,群體智能為尋找復雜的分布式問題的解決方案提供了基礎。常用的群體智能有蟻群優化算法、信息素算法、粒子群優化算法等。在半導體制造系統調度中,群體智能的應用相對較少。